case
28Mar/090

Sudoku solver in python

lens1512255_sudoku12Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid so that each column, each row, and each of the nine 3×3 boxes (also called blocks or regions) contains the digits from 1 to 9 only one time each. The puzzle setter provides a partially completed grid.
I'm really not a sudoku fan but I love solving problems and sudoku offers you a challenging one. So...here's a the shortest sudoku solver written in python

1
2
3
4
def r(a):i=a.find('0');~i or exit(a);[m
in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for
j in range(81)]or r(a[:i]+m+a[i+1:])for m in'%d'%5**18]
from sys import *;r(argv[1])

If you want to test that, save it in a file and use the command line to execute the code. Execute the code as following: python solver.py puzzle - where puzzle is an 81 character string representing the puzzle read left-to-right, top-to-bottom, and 0 is a blank space

python solver.py 530070000600195000098000060800060003400803001700020006060000280000419005000080079

The problem with the above code is that is really slow. Here's another one that runs about 100x faster and is less cryptic.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import sys
 
def same_row(i,j): return (i/9 == j/9)
def same_col(i,j): return (i-j) % 9 == 0
def same_block(i,j): return (i/27 == j/27 and i%9/3 == j%9/3)
 
def r(a):
  i = a.find('0')
  if i == -1:
    sys.exit(a)
 
  excluded_numbers = set()
  for j in range(81):
    if same_row(i,j) or same_col(i,j) or same_block(i,j):
      excluded_numbers.add(a[j])
 
  for m in '123456789':
    if m not in excluded_numbers:
      # At this point, m is not excluded by any row, column, or block, so let's place it and recurse
      r(a[:i]+m+a[i+1:])
 
if __name__ == '__main__':
  if len(sys.argv) == 2 and len(sys.argv[1]) == 81:
    r(sys.argv[1])
  else:
    print 'Usage: python sudoku.py puzzle'
Comments (0) Trackbacks (0)

No comments yet.


Leave a comment


CommentLuv badge

*

No trackbacks yet.