Naive Sudoku Solver.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Taken from https://www.hackerrank.com/contests/projecteuler/challenges/euler096/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Enter your code here. Read input from STDIN. Print output to STDOUT\n",
    "class SudokuSolver(object):\n",
    "    \n",
    "    def __init__(self, N=3, puzzle=None):\n",
    "        self.N = N\n",
    "        self.SIZE = self.N*self.N\n",
    "        self.puzzle = [[set([1])]*(self.SIZE)]*(self.SIZE)\n",
    "        if puzzle is None:\n",
    "            for i in range(self.SIZE):\n",
    "                self.puzzle[i] = [int(k) for k in raw_input()]\n",
    "        else:\n",
    "            self.puzzle = [[int(k) for k in line] for line in puzzle.splitlines()]\n",
    "\n",
    "        self._empty_cells = 0    \n",
    "        self._solutions = [[set([]) for i in range(self.SIZE)] for k in range(self.SIZE)]\n",
    "        #print self.puzzle\n",
    "        #print self._solutions\n",
    "        for i in range(self.SIZE):\n",
    "            for j in range(self.SIZE):\n",
    "                if self.puzzle[i][j] < 1:\n",
    "                    self._solutions[i][j] = set(range(1,self.SIZE+1))\n",
    "                    self._empty_cells += 1\n",
    "                    #print \"puzzle[%s][%s] = %s\\tsolutions[%s][%s] = %s\" % (i,j, self.puzzle[i][j], i, j, self._solutions[i][j])\n",
    "                else:\n",
    "                    self._solutions[i][j] = set([])\n",
    "        #print self._solutions\n",
    "\n",
    "\n",
    "    def get_remove_sets(self, i, j):\n",
    "        remove_items = []\n",
    "        remove_items.extend(self.puzzle[i]) # Row items\n",
    "        remove_items.extend([self.puzzle[k][j] for k in range(self.SIZE)]) # Col items\n",
    "        x, y = i/self.N, j/self.N\n",
    "        remove_items.extend([self.puzzle[x*self.N + (k/3)][y*self.N + (k%3)] \\\n",
    "                             for k in range(self.SIZE)]) # Square items\n",
    "        remove_set = set(remove_items) - set([0])\n",
    "        #print \"Remove_Set[%s][%s] = %s\" % (i, j, remove_set)\n",
    "        return remove_set\n",
    "    \n",
    "    def solve(self):\n",
    "        run_times = self.SIZE*self.SIZE\n",
    "        print \"Original with Empty Cells = %s\" % self._empty_cells\n",
    "        self.showSudoku()\n",
    "        changed_cell = True\n",
    "        #print \"Original Solution Table\"\n",
    "        #print self._solutions\n",
    "        #self.showSudoku(arr=self._solutions, sep=\"\\t\")\n",
    "        while(self._empty_cells > 0 and changed_cell):\n",
    "            # Row wise selection of solutions\n",
    "            #print \"Filling row wise\"\n",
    "            changed_cell = False\n",
    "            for i in range(self.SIZE):\n",
    "                for j in range(self.SIZE):\n",
    "                    if self.puzzle[i][j] != 0:\n",
    "                        continue\n",
    "                    remove_set = self.get_remove_sets(i, j)\n",
    "                    #print \"Before solutions[%s][%s] = %s, Remaining: %s\" % (i, j, self._solutions[i][j], self._empty_cells)\n",
    "                    self._solutions[i][j] -= remove_set\n",
    "                    #print \"After solutions[%s][%s] = %s, Remaining: %s\" % (i, j, self._solutions[i][j], self._empty_cells)\n",
    "                    if len(self._solutions[i][j]) == 1:\n",
    "                        self.puzzle[i][j] = self._solutions[i][j].pop()\n",
    "                        self._empty_cells -= 1\n",
    "                        changed_cell = True\n",
    "                        #print \"Adding puzzle[%s][%s] = %s, Remaining: %s\" % (i, j, puzzle[i][j], empty_cells)\n",
    "                        continue\n",
    "            run_times -= 1\n",
    "        print \"Solved with Empty Cells = %s\" % self._empty_cells\n",
    "        self.showSudoku()\n",
    "        \n",
    "    def solveRecurse(self, puzzle=None):\n",
    "        if puzzle is None:\n",
    "            puzzle = self.puzzle\n",
    "        found = False\n",
    "        for i in range(self.SIZE):\n",
    "            for j in range(self.SIZE):\n",
    "                if puzzle[i][j] == 0:\n",
    "                    found = True\n",
    "                    break\n",
    "            if found:\n",
    "                break\n",
    "        found_pos = (i, j)\n",
    "        if not found:\n",
    "            self.showSudoku(arr=puzzle)\n",
    "        \n",
    "        remove_set = self.get_remove_sets(i, j)\n",
    "        #print found_pos, remove_set\n",
    "        for m in range(1, self.SIZE+1):\n",
    "            if m not in remove_set:\n",
    "                #print \"Puttin %s at %s\" % (m, found_pos)\n",
    "                puzzle[found_pos[0]][found_pos[1]] = m\n",
    "                self.solveRecurse(puzzle=puzzle)\n",
    "        \n",
    "    \n",
    "    def showSudoku(self, arr = None, sep=\"\"):\n",
    "        if arr is None:\n",
    "            arr = self.puzzle\n",
    "        # Print final matrix\n",
    "        for i in range(self.SIZE):\n",
    "             print sep.join([str(k) for k in arr[i]])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "583927687\n",
      "987345001\n",
      "001806400\n",
      "008102900\n",
      "700000008\n",
      "006708200\n",
      "002609500\n",
      "800203009\n",
      "005010300\n"
     ]
    }
   ],
   "source": [
    "s = SudokuSolver(puzzle=\"003020600\\n900305001\\n001806400\\n008102900\\n700000008\\n006708200\\n002609500\\n800203009\\n005010300\")\n",
    "s.solveRecurse()\n",
    "s.showSudoku()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original with Empty Cells = 51\n",
      "200080300\n",
      "060070084\n",
      "030500209\n",
      "000105408\n",
      "000000000\n",
      "402706000\n",
      "301007040\n",
      "720040060\n",
      "004010003\n",
      "Solved with Empty Cells = 50\n",
      "200080300\n",
      "060070084\n",
      "030560209\n",
      "000105408\n",
      "000000000\n",
      "402706000\n",
      "301007040\n",
      "720040060\n",
      "004010003\n"
     ]
    }
   ],
   "source": [
    "p = \"\"\"200080300\n",
    "060070084\n",
    "030500209\n",
    "000105408\n",
    "000000000\n",
    "402706000\n",
    "301007040\n",
    "720040060\n",
    "004010003\"\"\"\n",
    "s = SudokuSolver(puzzle=p)\n",
    "s.solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Done\n"
     ]
    }
   ],
   "source": [
    "print \"Done\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Another implementation taken from: http://pythontips.com/2013/09/01/sudoku-solver-in-python/\n",
    "import sys\n",
    "\n",
    "def same_row(i,j): return (i/9 == j/9)\n",
    "def same_col(i,j): return (i-j) % 9 == 0\n",
    "def same_block(i,j): return (i/27 == j/27 and i%9/3 == j%9/3)\n",
    "\n",
    "def r(a):\n",
    "    i = a.find('0')\n",
    "    if i == -1:\n",
    "        print a\n",
    "        print \"\\n\".join([a[k*9:k*9+9] for k in range(9)])\n",
    "\n",
    "    excluded_numbers = set()\n",
    "    for j in range(81):\n",
    "        if same_row(i,j) or same_col(i,j) or same_block(i,j):\n",
    "            excluded_numbers.add(a[j])\n",
    "    #print i, i/9, i%9, excluded_numbers\n",
    "    \n",
    "    for m in '123456789':\n",
    "        if m not in excluded_numbers:\n",
    "            #print \"Puttin %s at %s, %s, %s\" % (m, i, i/9, i%9)\n",
    "            r(a[:i]+m+a[i+1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "245981376169273584837564219976125438513498627482736951391657842728349165654812793\n",
      "245981376\n",
      "169273584\n",
      "837564219\n",
      "976125438\n",
      "513498627\n",
      "482736951\n",
      "391657842\n",
      "728349165\n",
      "654812793\n"
     ]
    }
   ],
   "source": [
    "r(\"200080300060070084030500209000105408000000000402706000301007040720040060004010003\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "483921657967345821251876493548132976729564138136798245372689514814253769695417382\n",
      "483921657\n",
      "967345821\n",
      "251876493\n",
      "548132976\n",
      "729564138\n",
      "136798245\n",
      "372689514\n",
      "814253769\n",
      "695417382\n"
     ]
    }
   ],
   "source": [
    "r(\"003020600900305001001806400008102900700000008006708200002609500800203009005010300\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "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.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}