recursive sudoku solver - Jupyter Notebook

sudoku.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true,
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "# SUDOKU Solver",
    " [computerphile ▶️](https://youtu.be/G_UYXzGuqvM)"
   ]
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Problem"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n",
     "is_executing": false
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 621,
   "outputs": [
    {
     "name": "stdout",
     "text": [
      "[[5 3 0 0 7 0 0 0 0]\n",
      " [6 0 0 1 9 5 0 0 0]\n",
      " [0 9 8 0 0 0 0 6 0]\n",
      " [8 0 0 0 6 0 0 0 3]\n",
      " [4 0 0 8 0 3 0 0 1]\n",
      " [7 0 0 0 2 0 0 0 6]\n",
      " [0 6 0 0 0 0 2 8 0]\n",
      " [0 0 0 4 1 9 0 0 5]\n",
      " [0 0 0 0 8 0 0 0 9]]\n"
     ],
     "output_type": "stream"
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "grid = [[5, 3, 0, 0, 7, 0, 0, 0, 0],\n",
    "        [6, 0, 0, 1, 9, 5, 0, 0, 0],\n",
    "        [0, 9, 8, 0, 0, 0, 0, 6, 0],\n",
    "        [8, 0, 0, 0, 6, 0, 0, 0, 3],\n",
    "        [4, 0, 0, 8, 0, 3, 0, 0, 1],\n",
    "        [7, 0, 0, 0, 2, 0, 0, 0, 6],\n",
    "        [0, 6, 0, 0, 0, 0, 2, 8, 0],\n",
    "        [0, 0, 0, 4, 1, 9, 0, 0, 5],\n",
    "        [0, 0, 0, 0, 8, 0, 0, 0, 9]]\n",
    "\n",
    "# noinspection PyDeprecation\n",
    "print(np.matrix(grid))\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n",
     "is_executing": false
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 622,
   "outputs": [],
   "source": [
    "# check if you can put n at [y][x]\n",
    "def possible(y, x, n):\n",
    "    global grid\n",
    "    for i in range(0, 9):\n",
    "        if grid[y][i] == n :\n",
    "            return False\n",
    "    for i in range(0, 9):\n",
    "        if grid[i][x] == n :\n",
    "            return False\n",
    "    x0 = x - x%3 # (x//3) * 3\n",
    "    y0 = y - y%3 # (y//3) * 3\n",
    "    for i in range(0, 3):\n",
    "        for j in range(0, 3):\n",
    "            if grid[y0+i][x0+j] == n :\n",
    "                return False\n",
    "    return True\n",
    "  "
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n",
     "is_executing": false
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Solution"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%% md\n",
     "is_executing": false
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": 623,
   "outputs": [
    {
     "name": "stdout",
     "text": [
      "[[5 3 4 6 7 8 1 9 2]\n",
      " [6 7 2 1 9 5 3 4 8]\n",
      " [1 9 8 3 4 2 5 6 7]\n",
      " [8 5 9 7 6 1 4 2 3]\n",
      " [4 2 6 8 5 3 9 7 1]\n",
      " [7 1 3 9 2 4 8 5 6]\n",
      " [9 6 1 5 3 7 2 8 4]\n",
      " [2 8 7 4 1 9 6 3 5]\n",
      " [3 4 5 2 8 6 7 1 9]] \n",
      "\n",
      "[[5 3 4 6 7 8 9 1 2]\n",
      " [6 7 2 1 9 5 3 4 8]\n",
      " [1 9 8 3 4 2 5 6 7]\n",
      " [8 5 9 7 6 1 4 2 3]\n",
      " [4 2 6 8 5 3 7 9 1]\n",
      " [7 1 3 9 2 4 8 5 6]\n",
      " [9 6 1 5 3 7 2 8 4]\n",
      " [2 8 7 4 1 9 6 3 5]\n",
      " [3 4 5 2 8 6 1 7 9]] \n",
      "\n",
      "Recursions: 4897 \n",
      "\n",
      "CPU times: user 128 ms, sys: 3.96 ms, total: 132 ms\n",
      "Wall time: 134 ms\n"
     ],
     "output_type": "stream"
    }
   ],
   "source": [
    "%%time\n",
    "recursion = 0\n",
    "\n",
    "# recursive solve\n",
    "def solve():\n",
    "    global grid, recursion\n",
    "    recursion += 1\n",
    "    for y in range(0, 9) :\n",
    "        for x in range(0, 9) :\n",
    "            if grid[y][x] == 0 :\n",
    "                for n in range(1, 10) :\n",
    "                    if possible(y, x, n) :\n",
    "                        grid[y][x] = n\n",
    "                        solve()\n",
    "                        grid[y][x] = 0\n",
    "                return\n",
    "    # noinspection PyDeprecation\n",
    "    print(np.matrix(grid), \"\\n\")\n",
    "solve()\n",
    "print(f\"Recursions: {recursion}\", \"\\n\")\n",
    "\n"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "name": "#%%\n",
     "is_executing": false
    }
   }
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  },
  "pycharm": {
   "stem_cell": {
    "cell_type": "raw",
    "source": [],
    "metadata": {
     "collapsed": false
    }
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}