{ "metadata": { "name": "Sudoku solver" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "code", "collapsed": false, "input": [ "grid = array([2, 1, nan, 4, 3, nan, nan, 7, nan,\n", " nan, nan, nan, nan, nan, nan, 8, 5, nan,\n", " nan, nan, 4, nan, nan, 7, nan, 1, 3,\n", " nan, nan, nan, nan, nan, 2, nan, 9, 5,\n", " nan, nan, nan, 8, 1, 9, nan, nan, nan,\n", " 9, 6, nan, 7, nan, nan, nan, nan, nan,\n", " 8, 9, nan, 5, nan, nan, 7, nan, nan,\n", " nan, 2, 1, nan, nan, nan, nan, nan, nan,\n", " nan, 3, nan, nan, 7, 8, nan, 6, 9]).reshape((9, 9))\n", "grid" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "pyout", "prompt_number": 2, "text": [ "array([[ 2., 1., nan, 4., 3., nan, nan, 7., nan],\n", " [ nan, nan, nan, nan, nan, nan, 8., 5., nan],\n", " [ nan, nan, 4., nan, nan, 7., nan, 1., 3.],\n", " [ nan, nan, nan, nan, nan, 2., nan, 9., 5.],\n", " [ nan, nan, nan, 8., 1., 9., nan, nan, nan],\n", " [ 9., 6., nan, 7., nan, nan, nan, nan, nan],\n", " [ 8., 9., nan, 5., nan, nan, 7., nan, nan],\n", " [ nan, 2., 1., nan, nan, nan, nan, nan, nan],\n", " [ nan, 3., nan, nan, 7., 8., nan, 6., 9.]])" ] } ], "prompt_number": 2 }, { "cell_type": "code", "collapsed": false, "input": [ "class sudoku(object):\n", " def __init__(self, grid):\n", " self.grid = grid\n", " \n", " def try_cell(self, cell_index, debug=False):\n", " if not isnan(self.grid[cell_index]):\n", " if debug:\n", " print \"cell is already occupied! by %s\" % (self.grid[cell_index])\n", " return array([])\n", " else:\n", " if debug:\n", " print \"cell is not yet occupied:\", self.grid[cell_index]\n", " # rows and columns\n", " in_column = filter(lambda n: ~isnan(n), self.grid[:, cell_index[1]])\n", " in_row = filter(lambda n: ~isnan(n), self.grid[cell_index[0], :])\n", " if debug:\n", " print \"rows and columns contain:\", unique(hstack((in_row, in_column)))\n", " # 3 x 3 block cell\n", " block_coords = [n / 3 for n in cell_index]\n", " if debug:\n", " print block_coords\n", " in_block = self.grid[3 * block_coords[0]:3 * block_coords[0] + 3,\n", " 3 * block_coords[1]:3 * block_coords[1] + 3]\n", " in_block = in_block.reshape((1, 9))[0]\n", " in_block = filter(lambda n: ~isnan(n), in_block)\n", " if debug:\n", " print in_block\n", " already_taken = unique(hstack((in_row, in_column, in_block)))\n", " if debug:\n", " print already_taken\n", " return already_taken\n", " \n", " def solve_step(self):\n", " for i in range(self.grid.shape[0]):\n", " for j in range(self.grid.shape[1]):\n", " trial = self.try_cell((i, j))\n", " if trial.shape == (8,):\n", " self.grid[i, j] = 45 - sum(trial)\n", " print i, j, 45 - sum(trial)\n", " return True\n", " return False\n", " \n", " def solve(self):\n", " can_solve = True\n", " while can_solve:\n", " can_solve = self.solve_step()\n", " " ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 3 }, { "cell_type": "code", "collapsed": false, "input": [ "sdk = sudoku(grid)\n", "d = sdk.try_cell((0, 2))\n", "%time sdk.solve()\n", "sdk.grid" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "0 8 6.0\n", "0 5 5.0\n", "0 6 9.0\n", "0 2 8.0\n", "1 1 7.0\n", "2 1 5.0\n", "2 0 6.0\n", "1 0 3.0\n", "1 2 9.0\n", "2 6 2.0\n", "1 8 4.0\n", "2 3 9.0\n", "2 4 8.0\n", "4 1 4.0\n", "3 1 8.0\n", "6 2 6.0\n", "7" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " 8 8.0\n", "8 2 5.0\n", "8 0 4.0\n", "7 0 7.0\n", "3 0 1.0\n", "4 0 5.0\n", "8" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " 6 1.0\n", "6 8 2.0\n", "4 8 7.0\n", "5 8 1.0\n", "6 4 4.0\n", "3 4 6.0\n", "1 4 2.0\n", "3 3 3.0\n", "3 2 7.0\n", "3 6 4.0\n", "5 4 5.0\n", "5 5 4.0\n", "5" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " 6 3.0\n", "4 6 6.0\n", "4 7 2.0\n", "4 2 3.0\n", "5 2 2.0\n", "5 7 8.0\n", "6 7 3.0\n", "6 5 1.0\n", "1 5 6.0\n", "1 3 1.0\n", "7 3 6.0\n", "7 4 9.0\n", "7 5 3.0\n", "7 6 5.0\n", "7 7 4.0\n", "8 3 2.0\n", "CPU times: user 0.21 s, sys: 0.00 s, total: 0.21 s\n", "Wall time: 0.21 s\n" ] }, { "output_type": "pyout", "prompt_number": 4, "text": [ "array([[ 2., 1., 8., 4., 3., 5., 9., 7., 6.],\n", " [ 3., 7., 9., 1., 2., 6., 8., 5., 4.],\n", " [ 6., 5., 4., 9., 8., 7., 2., 1., 3.],\n", " [ 1., 8., 7., 3., 6., 2., 4., 9., 5.],\n", " [ 5., 4., 3., 8., 1., 9., 6., 2., 7.],\n", " [ 9., 6., 2., 7., 5., 4., 3., 8., 1.],\n", " [ 8., 9., 6., 5., 4., 1., 7., 3., 2.],\n", " [ 7., 2., 1., 6., 9., 3., 5., 4., 8.],\n", " [ 4., 3., 5., 2., 7., 8., 1., 6., 9.]])" ] } ], "prompt_number": 4 }, { "cell_type": "code", "collapsed": false, "input": [], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 4 }, { "cell_type": "code", "collapsed": false, "input": [], "language": "python", "metadata": {}, "outputs": [] } ], "metadata": {} } ] }