Sudoku.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solving Sudoku\n",
    "\n",
    "I'm going to attempt to solve Sudoku puzzles using 2 methods:\n",
    "\n",
    "* Linear Algebra\n",
    "    - When I first saw Sudoku years ago, the first thing I thought of was a system of linear equations - the puzzle is a matrix after all. So I want to explore the idea of writing a system of linear equations to describe a Sudoku puzzle, and use some numeric optimization algorithms to try to find a solution (by minimizing the \"error\").\n",
    "* Backtrack searching\n",
    "    - This is the most obvious and probably the best way to solve Sudoku\n",
    "    \n",
    "In both cases, we'll develop a solution on a 4x4 version of sudoku before moving to the normal 9x9 board.\n",
    "\n",
    "## Solving Sudoku with Linear Algebra\n",
    "\n",
    "### Pretty-print matrix function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table><tr><td>1</td><td>2</td></tr><tr><td>3</td><td>4</td></tr></table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 159,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from IPython.display import HTML\n",
    "\n",
    "def print_matrix(mat):\n",
    "    t = [\"<table>\"]\n",
    "    for row in mat:\n",
    "        t.append(\"<tr>\")\n",
    "        for col in row:\n",
    "            t.append(\"<td>\" + str(col) + \"</td>\")\n",
    "        t.append(\"</tr>\")\n",
    "    t.append(\"</table>\")\n",
    "    return HTML(''.join(t))\n",
    "\n",
    "print_matrix([[1,2],[3,4]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import random"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4x4 Sudoku\n",
    "\n",
    "<table class=\"invisible-table\"><tr><td>\n",
    "\n",
    "Puzzle\n",
    "<table class=\"padded-table\">\n",
    "<tr><td><b>1</b></td><td>&nbsp;</td><td>&nbsp;</td><td>&nbsp;</td></tr>\n",
    "<tr><td> </td><td>&nbsp;</td><td><b>4</b></td><td>&nbsp;</td></tr>\n",
    "<tr><td> </td><td><b>3</b></td><td>&nbsp;</td><td>&nbsp;</td></tr>\n",
    "<tr><td>&nbsp;</td><td>&nbsp;</td><td><b>2</b></td><td>&nbsp;</td></tr>\n",
    "</table>\n",
    "\n",
    "</td><td>\n",
    "\n",
    "Solution\n",
    "<table class=\"padded-table\">\n",
    "<tr><td>1</td><td>4</td><td>3</td><td>2</td></tr>\n",
    "<tr><td>3</td><td>2</td><td>4</td><td>1</td></tr>\n",
    "<tr><td>2</td><td>3</td><td>1</td><td>4</td></tr>\n",
    "<tr><td>4</td><td>1</td><td>2</td><td>3</td></tr>\n",
    "</table>\n",
    "\n",
    "</td></tr></table>\n",
    "\n",
    "<style>\n",
    ".padded-table td { padding: 15px; }\n",
    ".invisible-table { border: 0px; }\n",
    "</style>\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 161,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table><tr><td>a01</td><td>a02</td><td>a03</td><td>a04</td></tr><tr><td>a05</td><td>a06</td><td>a07</td><td>a08</td></tr><tr><td>a09</td><td>a10</td><td>a11</td><td>a12</td></tr><tr><td>a13</td><td>a14</td><td>a15</td><td>a16</td></tr></table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 161,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "m1 = [['a01', 'a02', 'a03', 'a04'],\n",
    "      ['a05', 'a06', 'a07', 'a08'],\n",
    "      ['a09', 'a10', 'a11', 'a12'],\n",
    "      ['a13', 'a14', 'a15', 'a16']]\n",
    "\n",
    "print_matrix(m1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### System of Equations to describe puzzle\n",
    "\n",
    "#### Sudoku-constant equations\n",
    "\n",
    "These first 12 equations are the same for all 4x4 sudoku puzzles - they are the rules of the game:\n",
    "\n",
    "By Rows:\n",
    "\n",
    "* a01 + a02 + a03 + a04 = 10\n",
    "* a05 + a06 + a07 + a08 = 10\n",
    "* a09 + a10 + a11 + a12 = 10\n",
    "* a13 + a14 + a15 + a16 = 10\n",
    "\n",
    "By Columns:\n",
    "\n",
    "* a01 + a05 + a09 + a13 = 10\n",
    "* a02 + a06 + a10 + a14 = 10\n",
    "* a03 + a07 + a11 + a15 = 10\n",
    "* a04 + a08 + a12 + a16 = 10\n",
    "\n",
    "By Quandrants:\n",
    "\n",
    "* a01 + a02 + a05 + a06 = 10\n",
    "* a03 + a04 + a07 + a08 = 10\n",
    "* a09 + a10 + a13 + a14 = 10\n",
    "* a11 + a12 + a15 + a16 = 10\n",
    "\n",
    "\n",
    "#### Puzzle-specific equations\n",
    "\n",
    "These last 4 equations are what we are given for this particular puzzle:\n",
    "\n",
    "* a01 = 1\n",
    "* a07 = 4\n",
    "* a10 = 3\n",
    "* a15 = 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 162,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "a =   [[1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
    "       [0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],\n",
    "       [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0],\n",
    "       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1],\n",
    "       \n",
    "       [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0],\n",
    "       [0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0],\n",
    "       [0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0],\n",
    "       [0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1],\n",
    "       \n",
    "       [1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
    "       [0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],\n",
    "       [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0],\n",
    "       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1],\n",
    "       \n",
    "       [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
    "       [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],\n",
    "       [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],\n",
    "       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]]\n",
    "\n",
    "b = [10, 10, 10, 10,  10, 10, 10, 10,  10, 10, 10, 10,  1, 4, 3, 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 163,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 1.        ,  3.47387651,  0.66316228,  4.86296121],\n",
       "       [ 3.92477232,  1.60135117,  4.        ,  0.47387651],\n",
       "       [ 2.04450137,  3.        ,  3.33683772,  1.61866091],\n",
       "       [ 3.03072631,  1.92477232,  2.        ,  3.04450137]])"
      ]
     },
     "execution_count": 163,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = np.linalg.lstsq(a,b)\n",
    "np.reshape(x[0], (4,-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1, 3, 1, 5],\n",
       "       [4, 2, 4, 0],\n",
       "       [2, 3, 3, 2],\n",
       "       [3, 2, 2, 3]])"
      ]
     },
     "execution_count": 164,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution = np.reshape([int(round(i)) for i in x[0]], (4, -1))\n",
    "solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linear Regression Implementation\n",
    "\n",
    "I wanted to implement my own linear regression algorithm to better understand how it works."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# TODO: Add precesion early break\n",
    "def linear_regression(a, b, precision=0.01, learning_rate=0.1, max_iters = 200):\n",
    "    m = len(b)\n",
    "    omega = np.ones(m)\n",
    "    \n",
    "    for iter in range(max_iters):\n",
    "        for i in range(m):\n",
    "            omega[i] = omega[i] - learning_rate * (1.0/m) * sum((np.dot(a, omega) - b) * a[i])\n",
    "        \n",
    "    return omega"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test problem to solve"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 166,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-5. ,  5.5])"
      ]
     },
     "execution_count": 166,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 3x+4y=7 and 5x+6y=8\n",
    "a1=[[3,4],[5,6]]\n",
    "b1=[7,8]\n",
    "linear_regression(a1,b1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Compare with numpy implementation's solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 167,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-4.9999999999999769, 5.4999999999999813)"
      ]
     },
     "execution_count": 167,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "((x,y),_,_,_) = np.linalg.lstsq(a1,b1)\n",
    "(x,y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([  4.71143849,   4.688242  ,   4.66519049,  -0.71713789,\n",
       "         1.9568043 ,  -6.86351593,   1.06255254,  17.08008666,\n",
       "        -1.34069241,  10.54590296,  -3.6327123 ,   7.43473406,\n",
       "        -0.87012213,   7.11479335,  -4.74101031,  -2.80275689])"
      ]
     },
     "execution_count": 168,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "result = linear_regression(a,b)\n",
    "result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Trying on Normal (9x9) Sudoku Puzzle"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table><tr><td>a0</td><td>a1</td><td>a2</td><td>a3</td><td>a4</td><td>a5</td><td>a6</td><td>a7</td><td>a8</td></tr><tr><td>a9</td><td>a10</td><td>a11</td><td>a12</td><td>a13</td><td>a14</td><td>a15</td><td>a16</td><td>a17</td></tr><tr><td>a18</td><td>a19</td><td>a20</td><td>a21</td><td>a22</td><td>a23</td><td>a24</td><td>a25</td><td>a26</td></tr><tr><td>a27</td><td>a28</td><td>a29</td><td>a30</td><td>a31</td><td>a32</td><td>a33</td><td>a34</td><td>a35</td></tr><tr><td>a36</td><td>a37</td><td>a38</td><td>a39</td><td>a40</td><td>a41</td><td>a42</td><td>a43</td><td>a44</td></tr><tr><td>a45</td><td>a46</td><td>a47</td><td>a48</td><td>a49</td><td>a50</td><td>a51</td><td>a52</td><td>a53</td></tr><tr><td>a54</td><td>a55</td><td>a56</td><td>a57</td><td>a58</td><td>a59</td><td>a60</td><td>a61</td><td>a62</td></tr><tr><td>a63</td><td>a64</td><td>a65</td><td>a66</td><td>a67</td><td>a68</td><td>a69</td><td>a70</td><td>a71</td></tr><tr><td>a72</td><td>a73</td><td>a74</td><td>a75</td><td>a76</td><td>a77</td><td>a78</td><td>a79</td><td>a80</td></tr></table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 169,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s9x9_flat = np.array(['a'+str(i) for i in range(81)])\n",
    "s9x9 = np.reshape(s9x9_flat, (9, -1))\n",
    "\n",
    "print_matrix(s9x9)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Generate equations (in matrix form)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "sudoku_base = []\n",
    "num_rows = 9\n",
    "num_cols = 9\n",
    "\n",
    "# Generate equations for rows\n",
    "for row in range(num_rows):\n",
    "    row_offset = num_rows * row\n",
    "    new_row = [0 for i in range(num_rows * num_cols)]\n",
    "    for i in range(num_rows):\n",
    "        new_row[row_offset + i] = 1\n",
    "    sudoku_base.append(new_row)\n",
    "\n",
    "# Generate equations for columns\n",
    "for col in range(num_cols):\n",
    "    col_offset = num_cols * col\n",
    "    new_row = [0 for i in range(num_rows * num_cols)]\n",
    "    for i in range(num_cols):\n",
    "        new_row[i * 9 + col] = 1\n",
    "    sudoku_base.append(new_row)\n",
    "\n",
    "# Generate equations for squares\n",
    "current_cell = 0\n",
    "for square_start in [0, 3, 6, 27, 30, 33, 54, 57, 60]:\n",
    "    new_row = [0 for i in range(num_rows * num_cols)]\n",
    "    for cell_offset in [0, 1, 2, 9, 10, 11, 18, 19, 20]:\n",
    "        new_row[square_start+cell_offset] = 1\n",
    "    sudoku_base.append(new_row)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# This is a wide matrix\n",
    "#print_matrix(sudoku_base)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Definition of sample puzzle\n",
    "puzzle1 = {0:8, 3:1, 4:6, 9:4, 10:1, \n",
    "          12:9, 14:8, 17:6, 25:1, 31:8, \n",
    "          32:6, 35:3, 37:8, 38:9, 40:3, \n",
    "          42:2, 43:5, 45:3, 48:2, 49:9, \n",
    "          55:2, 63:7, 66:8, 68:4, 70:6, \n",
    "          71:5, 76:5, 77:7, 80:4}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def print_puzzle(puzzle):\n",
    "    puzzle_mat = [' ' for i in range(81)]\n",
    "    for (k,v) in puzzle.items():\n",
    "        puzzle_mat[k] = v\n",
    "    return print_matrix(np.reshape(puzzle_mat, (9, -1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<table><tr><td>8</td><td> </td><td> </td><td>1</td><td>6</td><td> </td><td> </td><td> </td><td> </td></tr><tr><td>4</td><td>1</td><td> </td><td>9</td><td> </td><td>8</td><td> </td><td> </td><td>6</td></tr><tr><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td>1</td><td> </td></tr><tr><td> </td><td> </td><td> </td><td> </td><td>8</td><td>6</td><td> </td><td> </td><td>3</td></tr><tr><td> </td><td>8</td><td>9</td><td> </td><td>3</td><td> </td><td>2</td><td>5</td><td> </td></tr><tr><td>3</td><td> </td><td> </td><td>2</td><td>9</td><td> </td><td> </td><td> </td><td> </td></tr><tr><td> </td><td>2</td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td><td> </td></tr><tr><td>7</td><td> </td><td> </td><td>8</td><td> </td><td>4</td><td> </td><td>6</td><td>5</td></tr><tr><td> </td><td> </td><td> </td><td> </td><td>5</td><td>7</td><td> </td><td> </td><td>4</td></tr></table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 174,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print_puzzle(puzzle1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of equations: 45\n"
     ]
    }
   ],
   "source": [
    "print(\"Number of equations:\", len(puzzle1)+len(a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of unknowns: 52\n"
     ]
    }
   ],
   "source": [
    "print(\"Number of unknowns:\", 81 - len(puzzle1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def get_puzzle_rep(puzzle):\n",
    "    a = sudoku_base[:]\n",
    "    b = [sum(range(1,10)) for i in range(len(a))]\n",
    "    for (k,v) in puzzle.items():\n",
    "        new_a_row = [0 for i in range(81)]\n",
    "        new_a_row[k] = 1\n",
    "        a.append(new_a_row)\n",
    "        b.append(v)\n",
    "    return (a,b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 178,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "p1_a, p1_b = get_puzzle_rep(puzzle1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 179,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "56"
      ]
     },
     "execution_count": 179,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(p1_a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 180,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[  8,  75, -29,   1,   6,  -1, -10,  11, -15],\n",
       "       [  4,   1,  11,   9,   3,   8,   3,   0,   6],\n",
       "       [  6, -29,  -1,  17,   2,   0,  22,   1,  29],\n",
       "       [ -8,   1,  11,   6,   8,   6,  10,   9,   3],\n",
       "       [  8,   8,   9,  -6,   3,  11,   2,   5,   5],\n",
       "       [  3,   1,  14,   2,   9,   5,   1,   6,   4],\n",
       "       [  7,   2,  14,   6,   2,   5,  -1,   7,   4],\n",
       "       [  7, -11,  17,   8,   7,   4,   2,   6,   5],\n",
       "       [ 12,  -2,  -1,   2,   5,   7,  16,   1,   4]])"
      ]
     },
     "execution_count": 180,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = np.linalg.lstsq(p1_a,p1_b)\n",
    "solution = np.reshape([int(round(i)) for i in x[0]], (9, -1))\n",
    "solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Constrained Linear Regression - scipy.optimize.nnls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 181,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import scipy.optimize"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 182,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "result = scipy.optimize.nnls(p1_a, p1_b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[ 8, 30,  0,  1,  6,  0,  0,  0,  0],\n",
       "       [ 4,  1,  0,  9,  0,  8, 17,  0,  6],\n",
       "       [ 0,  2,  0,  0,  1, 20, 21,  1,  0],\n",
       "       [23,  0,  0,  0,  8,  6,  5,  0,  3],\n",
       "       [ 0,  8,  9, 17,  3,  0,  2,  5,  1],\n",
       "       [ 3,  2,  0,  2,  9,  0,  0,  3, 26],\n",
       "       [ 0,  2, 21,  8, 13,  0,  0,  1,  0],\n",
       "       [ 7,  0, 15,  8,  0,  4,  0,  6,  5],\n",
       "       [ 0,  0,  0,  0,  5,  7,  0, 29,  4]])"
      ]
     },
     "execution_count": 183,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution = np.reshape([int(round(i)) for i in result[0]], (9, -1))\n",
    "solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# scipy.optimize.fmin_slsqp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 184,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import scipy.optimize"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 185,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def objective_func(x):\n",
    "    mat_result = sum((np.dot(p1_a, x) - p1_b)**2)\n",
    "    #duplicate_count = 2 * sum([ (9 - len(set(x[row_start:row_start+9]))) for row_start in xrange(0, 81, 9)])\n",
    "    return mat_result # + duplicate_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 186,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4.833449373902292e-27"
      ]
     },
     "execution_count": 186,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "objective_func(result[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 187,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1672"
      ]
     },
     "execution_count": 187,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random_guess = [random.randint(1, 9) for i in range(81)]\n",
    "objective_func(random_guess)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 188,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Optimization terminated successfully.    (Exit mode 0)\n",
      "            Current function value: 2.29797100389e-07\n",
      "            Iterations: 32\n",
      "            Function evaluations: 2686\n",
      "            Gradient evaluations: 32\n"
     ]
    }
   ],
   "source": [
    "slsqp_result = scipy.optimize.fmin_slsqp(func=objective_func, x0=random_guess, bounds=[(1,9) for i in range(81)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 189,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 8.00003261,  6.35940875,  4.93648889,  1.00000169,  5.99997624,\n",
       "        4.29737636,  7.04763379,  3.92579154,  3.43323742,  3.99996711,\n",
       "        1.00004054,  2.86312341,  9.        ,  2.67226732,  8.00000642,\n",
       "        5.71913519,  5.74536874,  6.00004407,  5.37036786,  7.29314808,\n",
       "        5.17739899,  6.17573459,  5.39561016,  2.45905979,  5.88239592,\n",
       "        1.        ,  6.24634972,  3.72172385,  7.22664993,  4.04442496,\n",
       "        3.75455248,  7.99992386,  6.00006481,  3.23362232,  6.0189181 ,\n",
       "        3.00007657,  3.1967975 ,  7.99994184,  9.        ,  5.28159176,\n",
       "        3.00001894,  4.88903597,  1.99993536,  4.9999054 ,  4.63270593,\n",
       "        3.0000033 ,  3.1900495 ,  3.62047293,  1.99994369,  9.        ,\n",
       "        3.07474676,  7.94825758,  6.5796729 ,  6.58696652,  7.07995089,\n",
       "        1.99997988,  5.20345885,  5.29346834,  2.51483276,  5.27972021,\n",
       "        5.92777755,  5.60008543,  6.10076261,  6.99997325,  4.10688862,\n",
       "        3.74539955,  8.00006622,  3.41739541,  4.00005442,  3.73028178,\n",
       "        5.9999851 ,  4.99999989,  3.63107425,  5.8239441 ,  6.40926133,\n",
       "        4.49461762,  5.00000789,  6.99994006,  3.51079067,  5.13024736,\n",
       "        4.00007619])"
      ]
     },
     "execution_count": 189,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "slsqp_result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 190,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[8, 6, 5, 1, 6, 4, 7, 4, 3],\n",
       "       [4, 1, 3, 9, 3, 8, 6, 6, 6],\n",
       "       [5, 7, 5, 6, 5, 2, 6, 1, 6],\n",
       "       [4, 7, 4, 4, 8, 6, 3, 6, 3],\n",
       "       [3, 8, 9, 5, 3, 5, 2, 5, 5],\n",
       "       [3, 3, 4, 2, 9, 3, 8, 7, 7],\n",
       "       [7, 2, 5, 5, 3, 5, 6, 6, 6],\n",
       "       [7, 4, 4, 8, 3, 4, 4, 6, 5],\n",
       "       [4, 6, 6, 4, 5, 7, 4, 5, 4]])"
      ]
     },
     "execution_count": 190,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "z = np.reshape([int(round(i)) for i in slsqp_result], (9, -1))\n",
    "z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 191,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.2979710038864857e-07"
      ]
     },
     "execution_count": 191,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "objective_func(slsqp_result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Genetic Algorithm\n",
    "\n",
    "The fmin_slsqp result seemed so close, I was curious if running the GA on its output would tweak the last few values into place.  It turns out not to work."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 192,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def sudoku_fitness(a, b, attempt):\n",
    "    return sum((np.dot(a, attempt) - b)**2)\n",
    "\n",
    "def sudoku_mutation_swap(current, max_mutations=3):\n",
    "    num_mutations = random.randint(1, max_mutations)\n",
    "    baby = current[:]\n",
    "    for i in range(num_mutations):\n",
    "        index1 = random.randint(0,80)\n",
    "        index2 = random.randint(0,80)\n",
    "        baby[index1], baby[index2] = baby[index2], baby[index1]\n",
    "    return baby\n",
    "\n",
    "def sudoku_mutation_tweak(current, max_mutations=3):\n",
    "    num_mutations = random.randint(1, max_mutations)\n",
    "    baby = current[:]\n",
    "    for i in range(max_mutations):\n",
    "        index1 = random.randint(0,80)\n",
    "        index2 = random.randint(0,80)\n",
    "        tweak_amount = random.randint(1, 3)\n",
    "        baby[index1] = ((baby[index1]+tweak_amount) % 9) + 1\n",
    "        baby[index2] = ((baby[index2]+tweak_amount) % 9) + 1\n",
    "    return baby\n",
    "\n",
    "def sudoku_genetic_algorithm(fitness_func, mutation_func, initial_guess=None, max_iters=1000):\n",
    "    iter_count = 0\n",
    "    error_steps = []\n",
    "    current = np.array([i for i in range(1,10) for j in range(1,10)])\n",
    "    current_fitness = 100000000 # really big - assume the guess is really bad\n",
    "\n",
    "    if initial_guess != None:\n",
    "        current = initial_guess[:]\n",
    "        current_fitness = fitness_func(current)\n",
    "    \n",
    "    for i in range(max_iters):\n",
    "        baby = mutation_func(current)\n",
    "        baby_fitness = fitness_func(baby)\n",
    "        \n",
    "        # If we found a perfect solution, just return it!\n",
    "        if baby_fitness == 0:\n",
    "            return (baby, 0)\n",
    "        \n",
    "        # Compare baby fitness to current\n",
    "        elif baby_fitness < current_fitness:\n",
    "            print(\"Doing switch: baby_fitness=%d, current_fitness=%d\" % (baby_fitness, current_fitness))\n",
    "            current = baby[:]\n",
    "            current_fitness = baby_fitness\n",
    "        \n",
    "        iter_count += 1\n",
    "        if iter_count % 10000 == 0:\n",
    "            print(\"Error (steps=%d): %d\" % (iter_count, current_fitness))\n",
    "            error_steps.append(current_fitness)\n",
    "            \n",
    "    return (current, error_steps)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 193,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Initial fitness: 17\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/usr/local/lib/python3.5/site-packages/ipykernel/__main__.py:30: FutureWarning: comparison to `None` will result in an elementwise object comparison in the future.\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Error (steps=10000): 17\n",
      "Error (steps=20000): 17\n",
      "Error (steps=30000): 17\n",
      "Error (steps=40000): 17\n",
      "Error (steps=50000): 17\n"
     ]
    }
   ],
   "source": [
    "initial_g = np.array([int(round(i)) for i in slsqp_result])\n",
    "fitness = lambda attempt: sudoku_fitness(p1_a, p1_b, attempt)\n",
    "print(\"Initial fitness:\", fitness(initial_g))\n",
    "(ga_result, ga_error) = sudoku_genetic_algorithm(fitness, sudoku_mutation_tweak, initial_guess=initial_g, max_iters=50000)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 194,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[8, 6, 5, 2, 8, 8, 6, 7, 7],\n",
       "       [3, 8, 5, 2, 6, 2, 2, 3, 8],\n",
       "       [7, 3, 9, 2, 4, 1, 5, 3, 2],\n",
       "       [4, 3, 7, 1, 2, 2, 3, 2, 4],\n",
       "       [5, 3, 7, 3, 7, 6, 3, 1, 1],\n",
       "       [4, 3, 1, 5, 8, 5, 5, 8, 9],\n",
       "       [5, 4, 7, 6, 6, 5, 7, 5, 2],\n",
       "       [8, 2, 3, 1, 1, 5, 7, 8, 9],\n",
       "       [7, 6, 9, 8, 9, 4, 9, 2, 6]])"
      ]
     },
     "execution_count": 194,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.reshape([int(round(i)) for i in ga_result], (9, -1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 195,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[8, 6, 5, 2, 8, 8, 6, 7, 7],\n",
       "       [3, 8, 5, 2, 6, 2, 2, 3, 8],\n",
       "       [7, 3, 9, 2, 4, 1, 5, 3, 2],\n",
       "       [4, 3, 7, 1, 2, 2, 3, 2, 4],\n",
       "       [5, 3, 7, 3, 7, 6, 3, 1, 1],\n",
       "       [4, 3, 1, 5, 8, 5, 5, 8, 9],\n",
       "       [5, 4, 7, 6, 6, 5, 7, 5, 2],\n",
       "       [8, 2, 3, 1, 1, 5, 7, 8, 9],\n",
       "       [7, 6, 9, 8, 9, 4, 9, 2, 6]])"
      ]
     },
     "execution_count": 195,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.reshape([int(round(i)) for i in initial_g], (9, -1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "# Backtracking\n",
    "\n",
    "Okay, enough messing around; let's do it the right way now: backtracking.\n",
    "\n",
    "### Define the representation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 196,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "N = None\n",
    "puzzle = [[1, N, N, N],\n",
    "          [N, N, 4, N],\n",
    "          [N, 3, N, N],\n",
    "          [N, N, 2, N]]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### has_duplicates\n",
    "\n",
    "This function returns true if there are no duplicates in the list. We'll use it to determine if a possible solution is breaking any rules of sudoku - that there are duplicate numbers in either a row, column, or \"section\" (board quandrant for a 4x4 board)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 197,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def has_duplicates(lst):\n",
    "    seen = set()\n",
    "    for i in lst:\n",
    "        if i is not None:\n",
    "            if i in seen:\n",
    "                return True\n",
    "            else:\n",
    "                seen.add(i)\n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 198,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 198,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "has_duplicates([1,2,3,4,5])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 199,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 199,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "has_duplicates([1,2,3,4,5,1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### get_row"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 200,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_row(board, index):\n",
    "    return board[index]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 201,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, None, None, None]"
      ]
     },
     "execution_count": 201,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_row(puzzle, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### get_column"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 202,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_column(board, index):\n",
    "    return [board[i][index] for i in range(len(board))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 203,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, None, None, None]"
      ]
     },
     "execution_count": 203,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_column(puzzle, 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### get_section"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 204,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def get_section(board, index):\n",
    "    sqrt = int(math.sqrt(len(board)))\n",
    "    start_row = (index // sqrt) * sqrt\n",
    "    start_col = (index % sqrt) * sqrt\n",
    "    section = []\n",
    "    for i in range(sqrt):\n",
    "        section += board[start_row][start_col:start_col+sqrt]\n",
    "        start_row += 1\n",
    "    return section"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 205,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[None, None, 2, None]"
      ]
     },
     "execution_count": 205,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_section(puzzle, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### copy_and_set\n",
    "\n",
    "Return a new board with the specified value set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 206,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def copy_and_set(board, row, col, value):\n",
    "    board_new = [row.copy() for row in board]\n",
    "    board_new[row][col] = value\n",
    "    return board_new"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 207,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[1, 1, None, None],\n",
       " [None, None, 4, None],\n",
       " [None, 3, None, None],\n",
       " [None, None, 2, None]]"
      ]
     },
     "execution_count": 207,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "copy_and_set(puzzle, 0, 1, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### is_valid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 208,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def is_valid(board):\n",
    "    for row_index in range(len(board)):\n",
    "        row = get_row(board, row_index)\n",
    "        if has_duplicates(row):\n",
    "            return False\n",
    "    for col_index in range(len(board)):\n",
    "        col = get_column(board, col_index)\n",
    "        if has_duplicates(col):\n",
    "            return False\n",
    "    for section_index in range(len(board)):\n",
    "        section = get_section(board, section_index)\n",
    "        if has_duplicates(section):\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 209,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 209,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# This should be not be valid, since it would be 2 '1's in the first row\n",
    "is_valid(copy_and_set(puzzle, 0, 1, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 210,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 210,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# This should be valid, since there are no duplicates in any rows, columns, or sections\n",
    "is_valid(copy_and_set(puzzle, 0, 1, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 211,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 211,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# This should not be valid because there are duplicate '1's in the first column\n",
    "is_valid(copy_and_set(puzzle, 2, 0, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 212,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 212,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# This should not be valid because there are duplicate '1's in the first section\n",
    "is_valid(copy_and_set(puzzle, 1, 1, 1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### solve_sudoku"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 213,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def solve_sudoku(board, index=0):\n",
    "    row_index = index // len(board)\n",
    "    col_index = index % len(board)\n",
    "    \n",
    "    if (index > len(board)**2 - 1) or \\\n",
    "       (index == len(board)**2 - 1 and board[row_index][col_index] is not None):\n",
    "        if is_valid(board):\n",
    "            print('Solution found!')\n",
    "            return board\n",
    "        else:\n",
    "            # No solution to this puzzle\n",
    "            print('No solution to puzzle')\n",
    "            return None\n",
    "        \n",
    "    if board[row_index][col_index] != None:     \n",
    "        # Meaning it's a hard-coded value in the puzzle\n",
    "        return solve_sudoku(board, index+1)\n",
    "    \n",
    "    for num in range(1, len(board)+1):\n",
    "        with_num_set = copy_and_set(board, row_index, col_index, num)\n",
    "        if is_valid(with_num_set):\n",
    "            solution_or_none = solve_sudoku(with_num_set, index+1)\n",
    "            if solution_or_none is not None:\n",
    "                return solution_or_none\n",
    "\n",
    "    # No solution found on this path\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 214,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution found!\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([[1, 4, 3, 2],\n",
       "       [3, 2, 4, 1],\n",
       "       [2, 3, 1, 4],\n",
       "       [4, 1, 2, 3]])"
      ]
     },
     "execution_count": 214,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution = solve_sudoku(puzzle)\n",
    "np.reshape(solution, (4, -1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Let's try the backtracking solution on a 9x9 now"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 215,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "p_9x9 = [[8, N, N, 1, 6, N, N, N, N],\n",
    "         [4, 1, N, 9, N, 8, N, N, 6],\n",
    "         [N, N, N, N, N, N, N, 1, N],\n",
    "         [N, N, N, N, 8, 6, N, N, 3],\n",
    "         [N, 8, 9, N, 3, N, 2, 5, N],\n",
    "         [3, N, N, 2, 9, N, N, N, N],\n",
    "         [N, 2, N, N, N, N, N, N, N],\n",
    "         [7, N, N, 8, N, 4, N, 6, 5],\n",
    "         [N, N, N, N, 5, 7, N, N, 4]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 216,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution found!\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "array([[8, 3, 5, 1, 6, 2, 7, 4, 9],\n",
       "       [4, 1, 2, 9, 7, 8, 5, 3, 6],\n",
       "       [9, 7, 6, 5, 4, 3, 8, 1, 2],\n",
       "       [2, 5, 1, 7, 8, 6, 4, 9, 3],\n",
       "       [6, 8, 9, 4, 3, 1, 2, 5, 7],\n",
       "       [3, 4, 7, 2, 9, 5, 6, 8, 1],\n",
       "       [5, 2, 4, 6, 1, 9, 3, 7, 8],\n",
       "       [7, 9, 3, 8, 2, 4, 1, 6, 5],\n",
       "       [1, 6, 8, 3, 5, 7, 9, 2, 4]])"
      ]
     },
     "execution_count": 216,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solution = solve_sudoku(p_9x9)\n",
    "np.reshape(solution, (9, -1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Conclusion\n",
    "\n",
    "So backtracking, unsurprisingly, works well. But still, it was cool to see what Sudoku looks like as a system of equations right? :)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}