Sudoko Solver using Backtracking.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Sudoko Solver using Backtracking"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Dimensions of Sudoko Board\n",
    "# 9x9 Sudoko Board\n",
    "# 81 Numbers\n",
    "# 1-9 Digits are Allowed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Dimension of each subboard = 3x3\n",
    "subboardDim = 3\n",
    "\n",
    "# Dimension of Sudoko Board\n",
    "# 9x9 Board will contain 9 subboards\n",
    "boardDim = 9\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "sudokoBoard = [\n",
    "               [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,7,9]\n",
    "              ]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "numAllowed = list(range(1,10,1))\n",
    "print(numAllowed)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Function Definitions"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Function to Print Sudoko Board\n",
    "def displayBoard(sudokoBoard):\n",
    "    for i in sudokoBoard:\n",
    "        for j in i:\n",
    "            print(j,end=\" \")\n",
    "        print()\n",
    "    print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Function to check if the cell is empty or not\n",
    "\n",
    "def isEmpty(sudokoBoard,row,column):\n",
    "    # Check if the sudoko cell is valid\n",
    "    # Check the following conditions\n",
    "    # The cell should not contain any number, it should be either empty or should contain 0\n",
    "    return not sudokoBoard[row][column]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Function to check if the value is allowed in the cell\n",
    "\n",
    "def isValid(sudokoBoard,row,column,value):\n",
    "    # Check if value exist in the row\n",
    "    # Check if value exist in the column\n",
    "    # Check if the value exist in the Sudoko Subboard\n",
    "    for i in range(0,boardDim):\n",
    "        if(sudokoBoard[row][i] == value):\n",
    "            return False\n",
    "        \n",
    "    for i in range(0,boardDim):\n",
    "        if(sudokoBoard[i][column] == value):\n",
    "            return False\n",
    "    \n",
    "    # Dimensions of Sudoko Subboard\n",
    "    subBoardRow = row//subboardDim\n",
    "    subBoardCol = column//subboardDim\n",
    "    \n",
    "    for i in range(subBoardRow*subboardDim,(subBoardRow+1)*subboardDim,1):\n",
    "        for j in range(subBoardCol*subboardDim,(subBoardCol+1)*subboardDim,1):\n",
    "            if(sudokoBoard[i][j] == value):\n",
    "                return False\n",
    "            \n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Function to solve Sudoko Problem\n",
    "\n",
    "def sudokoSolver(sudokoBoard,row,column):\n",
    "    if row >= boardDim:\n",
    "        displayBoard(sudokoBoard)\n",
    "    \n",
    "    else:\n",
    "        if(isEmpty(sudokoBoard,row,column)):\n",
    "            for i in numAllowed:\n",
    "                if(isValid(sudokoBoard,row,column,i)):\n",
    "                    sudokoBoard[row][column] = i\n",
    "                    \n",
    "                    # Proceed for next cell\n",
    "                    if column < boardDim - 1:\n",
    "                        sudokoSolver(sudokoBoard,row,column+1)\n",
    "                    elif column == boardDim - 1:\n",
    "                        sudokoSolver(sudokoBoard,row+1,0)\n",
    "                \n",
    "                        \n",
    "                    # Backtracking Step\n",
    "                    sudokoBoard[row][column] = 0\n",
    "            \n",
    "        elif(not isEmpty(sudokoBoard,row,column)):\n",
    "            if column < boardDim - 1:\n",
    "                        sudokoSolver(sudokoBoard,row,column+1)\n",
    "            elif column == boardDim - 1:\n",
    "                sudokoSolver(sudokoBoard,row+1,0)\n",
    "            \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original Sudoko Board:\n",
      "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 7 9 \n",
      "\n",
      "Sudoko Solver:\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"
     ]
    }
   ],
   "source": [
    "# Display Sudoko Board\n",
    "print(\"Original Sudoko Board:\")\n",
    "displayBoard(sudokoBoard)\n",
    "\n",
    "# Sudoko Solver\n",
    "print(\"Sudoko Solver:\")\n",
    "sudokoSolver(sudokoBoard,0,0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}