| elioncho
| Joined: 04 Apr 2008 | Posts: 1 | : | | Items |
|
Posted: Fri Apr 04, 2008 6:41 am Post subject: Help deciphering a code |
|
|
Hi, I have this python code for a sudoku solver. Can anyone help me understand it line by line. Thanks
Code: |
03:
04: Usage: python sudoku.py filename
05:
06: where `filename' contains a textual representation of the sudoku, with unknown
07: values replaced by zeros. Something like:
08:
09: 5 3 0 0 7 0 0 0 0
10: 6 0 0 1 9 5 0 0 0
11: 0 9 8 0 0 0 0 6 0
12: 8 0 0 0 6 0 0 0 3
13: 4 0 0 8 0 3 0 0 1
14: 7 0 0 0 2 0 0 0 6
15: 0 6 0 0 0 0 2 8 0
16: 0 0 0 4 1 9 0 0 5
17: 0 0 0 0 8 0 0 7 9
18:
19: would be valid.
20:
21: This implements a _very_ simple backtracking recursive solver, using in-place,
22: iterative value replacement -- this problem is NP-hard anyway. Please note that
23: the solver will always find the first solution assuming there is one, then stop.
24: """
25: class Sudoku(list):
26: def __init__(self, filename):
27: list.__init__(self,
28: [d[i*9:(i+1)*9]
29: for i in range(9)
30: for d in [[int(e) for e in file(filename,'r').read().split()]]])
31: def __repr__(self):
32: return '\n'.join([' '.join([str(c) for c in r]) for r in self])
33: def grp(self, i, j):
34: return set((self[i][:] +
35: [self[k][j] for k in range(9)] +
36: [self[k][l]
37: for k in range(i/3*3, i/3*3+3)
38: for l in range(j/3*3, j/3*3+3)]))
39: def next(self, i, j): return (i*9+j+1)/9, (i*9+j+1)%9
40: def loop(self, i, j):
41: if i<9>=9: break
45: yield i, j
46:
47: def solve(s, k=0, l=0):
48: """Backtracking solver"""
49: for i, j in s.loop(k, l):
50: if s[i][j] is 0:
51: for val in set(range(1, 10)).difference(s.grp(i, j)):
52: s[i][j]=val
53: if solve(s,*s.next(i, j)): return s
54: s[i][j]=0
55: return
56: return s
57:
58: # Now, let's roll
59: from sys import argv
60: print solve(Sudoku(argv[1]))
| [/code] |
|