Monday, May 14, 2007

Ok i confess i'm lazy and i like python so what good might come out of this. Yeess, oh yes an automated sudoku-python-solver. The ultimate lame implementation of a sudoku solving algorithm in python, done in an hour or two it's not capable YET of solving sudokus with more than one solution but it'll do the job for that thick whole-year-list-a-day-sudoku-calendar. So here it goes, like this:

    1 #!/usr/bin/env python
2
3 class box:
4 #value 0 means empty
5 #numP
6 pass
7
8
9 class Board:
10 def __init__(self, rows=9, cols=9):
11 self.rows = rows
12 self.cols = cols
13 print av
14 self.board = []
15 for i in range(0, rows):
16 self.board.append( self.MakeRow(size=cols) )
17
18 def MakeRow(self, size=9):
19 r = []
20 for i in range(0, size):
21 r.append( box() )
22
23 return r
24
25 def InitBoard(self, data=[]):
26 rw = 0
27 cl = 0
28
29 for e in data:
30 self.board[rw][cl].value = e
31 cl = cl + 1
32
33 if cl == self.cols:
34 cl = 0;
35 rw = rw + 1
36
37 def GetRCInfo(self, row, col):
38 r = []
39 c = []
40 sq = []
41
42 for i in range(0, self.cols):
43 r.append( self.board[row][i].value )
44
45 for i in range(0, self.rows):
46 c.append( self.board[i][col].value )
47
48 br = (row/3)*3
49 bc = (col/3)*3
50
51 for sqR in range(br, br+3):
52 for sqC in range(bc, bc+3):
53 sq.append( self.board[sqR][sqC].value )
54
55 all = []
56
57 for i in r:
58 if all.__contains__(i):
59 continue
60 all.append(i)
61
62 for i in c:
63 if all.__contains__(i):
64 continue
65 all.append(i)
66
67 for i in sq:
68 if all.__contains__(i):
69 continue
70 all.append(i)
71
72 all.sort()
73 all.remove(0)
74
75 left = [1,2,3,4,5,6,7,8,9]
76 for i in all:
77 left.remove(i)
78
79 return left
80
81 def PrintBoard(self):
82 for rw in range(0,self.rows):
83 for cl in range(0, self.cols):
84 print self.board[rw][cl].value, " ",
85 print
86 print
87
88
89 def Solve(self):
90 done = False
91 while done != True:
92
93 for r in range(0, self.rows):
94 for c in range(0, self.cols):
95 if self.board[r][c].value == 0:
96 av = self.GetRCInfo(r,c)
97 if av.__len__() == 1:
98 self.board[r][c].value = av[0]
99 print "Adding ", av, " coords row:", r, " col:", c
100 self.PrintBoard()
101
102
103 done = True
104 for r in range(0,self.rows):
105 for c in range(0, self.cols):
106 if self.board[r][c].value == 0:
107 done = False
108 break
109
110 b = Board(9,9)
111 b.InitBoard([ 0,6,0,0,0,1,3,0,0,
112 0,5,0,6,0,9,1,0,0,
113 0,0,0,5,2,0,0,7,0,
114 0,0,0,0,0,2,6,0,7,
115 5,4,8,0,0,7,2,0,0,
116 0,0,0,9,1,8,0,5,0,
117 6,0,0,0,0,0,0,0,2,
118 0,0,5,0,0,0,7,0,0,
119 9,1,7,0,0,0,0,6,8
120 ])
121
122 b.PrintBoard()
123 print b.Solve()
124
125