solving_sudoku_recursion.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def possible(y,x,n):\n",
    "    global grid\n",
    "    for i in range(0,9):\n",
    "        #print(y,i,grid[y][i])\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//3)*3\n",
    "    y0 = (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",
    "\n",
    "def solve():\n",
    "    global grid\n",
    "    for y in range(9):\n",
    "        for x in range(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",
    "    print(np.matrix(grid))\n",
    "    input('More ?')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[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",
      "More ?\n"
     ]
    }
   ],
   "source": [
    "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,0,0,0,7,9]]\n",
    "\n",
    "solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[4 5 6 2 1 9 3 7 8]\n",
      " [3 9 2 7 8 5 6 1 4]\n",
      " [7 1 8 3 4 6 9 2 5]\n",
      " [9 6 3 8 7 4 2 5 1]\n",
      " [5 8 1 9 6 2 4 3 7]\n",
      " [2 4 7 1 5 3 8 6 9]\n",
      " [1 3 4 5 2 8 7 9 6]\n",
      " [6 2 5 4 9 7 1 8 3]\n",
      " [8 7 9 6 3 1 5 4 2]]\n",
      "More ?\n"
     ]
    }
   ],
   "source": [
    "grid = [[0,0,0,2,0,9,0,0,0],\n",
    "        [0,9,0,7,0,5,0,1,0],\n",
    "        [0,1,0,0,0,0,0,2,0],\n",
    "        [0,0,3,0,0,0,2,0,0],\n",
    "        [5,0,0,9,0,2,0,0,7],\n",
    "        [0,0,7,0,0,0,8,0,0],\n",
    "        [0,3,0,0,0,0,0,9,0],\n",
    "        [0,2,0,4,0,7,0,8,0],\n",
    "        [0,0,0,6,0,1,0,0,0]]\n",
    "\n",
    "#print(possible(4,4,5))\n",
    "solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}