Hi,
I am reading a python program now but I just cannot understand how the
values of class attributes are assigned and changed. Here is the original
code url:
Here I am concerned is how attribute matrix.rows is changed. Through pdb
debugging, I can see in line 97, once "self.solut ions = set((val,))" is
executed, cell.row and matrix.rows will be updated. But I did not see any
assignment codes here. How could this change happen then? Thanks a lot!
John
# http://agolb.blogspot.com/2006/01/su...in-python.html
#!/usr/bin/env python
#
# sudoku-solver version 3
#
# Some ideas ripped-off from:
# http://www.linuxjournal.com/article/8729
# http://aspn.activestate.com/ASPN/Coo.../Recipe/440542
# Pavol solver in
#
#
# Copyright 2005 Ago,
# But you are free to copy, reuse, modify and distribute the code as you see
fit
from copy import deepcopy
class DeadEnd(Excepti on): pass
class Matrix:
def __init__(self, input):
self.rows = [[] for i in range(9)]
self.cols = [[] for i in range(9)]
self.submatrice s = [[] for i in range(9)]
self.cells = [Cell(i,self) for i in range(81)]
self.subdiagona ls = [self.rows[i][j+i%3] for i in range(9) for j in
[0,3,6]]
input = [s not in '-*' and int(s) or 0 for s in input if s in
'0123456789-*']
for cell,val in zip(self.cells, input):
if val: cell.setSolutio n(val)
def solve(self): #Brute-force solver
self.solveByRed uction()
lensols=[(len(c.solution s),c.index) for c in self.cells if not
c.solved]
if not lensols: return True
unsolved = min(lensols)[1]
solutions = list(self.cells[unsolved].solutions)
for s in solutions:
tmpmatrix = deepcopy(self)
try:
tmpmatrix.cells[unsolved].setSolution(s)
if tmpmatrix.solve ():
self.update(tmp matrix)
return True
except DeadEnd: pass
def solveByReductio n(self):
while True:
self.changed = False
for c in self.cells: c.solve()
for c in self.subdiagona ls: c.skim()
if not self.changed: break
def update(self, m):
self.rows, self.cols, self.submatrice s, self.cells,
self.subdiagona ls=\
m.rows, m.cols, m.submatrices, m.cells, m.subdiagonals
def __str__(self):
return "\n".join(s tr([c for c in row ])[1:-1] for row in self.rows)
class Cell:
def __init__(self, index, matrix):
self.solved = False
self.matrix = matrix
self.index = index
self.row = matrix.rows[index/9]
self.col = matrix.cols[index%9]
self.submatrix = matrix.submatri ces[((index/9)/3)*3+(index%9)/3]
self.row.append (self)
self.col.append (self)
self.submatrix. append(self)
self.solutions = set(range(1,10) )
def solve(self):
if self.solved: return
if len(self.soluti ons) == 1:
self.setSolutio n(self.solution s.pop())
else:
sol = set()
for cells in [self.row, self.col, self.submatrix]:
otherSolutions = self.cells2sols (cells, self)
sol |= (self.solutions - otherSolutions)
if len(sol) 1: raise DeadEnd()
if sol: self.setSolutio n(sol.pop())
def skim(self):
submatrix = set(self.submat rix)
for r in (set(self.row), set(self.col)):
subset1 = submatrix - r
subset2 = r - submatrix
solsNotIn1 = set(range(1,10) ) - self.cells2sols (subset2)
solsNotIn2 = set(range(1,10) ) - self.cells2sols (subset1)
for c in subset1: c.delSolutions( solsNotIn1)
for c in subset2: c.delSolutions( solsNotIn2)
def setSolution(sel f, val):
self.solved = True
self.solutions = set((val,))
self.matrix.cha nged = True
for other in self.row+self.c ol+self.submatr ix:
if other is self: continue
if other.solutions == self.solutions: raise DeadEnd()
other.delSoluti ons(self.soluti ons)
def delSolutions(se lf, val):
if not self.solved and val & self.solutions:
self.solutions -= val
self.matrix.cha nged = True
if not self.solutions: raise DeadEnd()
def __repr__(self):
return str(self.solved and list(self.solut ions)[0] or
list(self.solut ions))
@staticmethod
def cells2sols(cell s, exclude=None):
return set(s for c in cells for s in c.solutions if c is not
exclude)
if __name__ == "__main__":
input ='''
1,0,0,0,0,0,0,0 ,2
0,9,0,4,0,0,0,5 ,0
0,0,6,0,0,0,7,0 ,0
0,5,0,9,0,3,0,0 ,0
0,0,0,0,7,0,0,0 ,0
0,0,0,8,5,0,0,4 ,0
7,0,0,0,0,0,6,0 ,0
0,3,0,0,0,9,0,8 ,0
0,0,2,0,0,0,0,0 ,1
'''
matrix = Matrix(input)
matrix.solve()
print matrix
I am reading a python program now but I just cannot understand how the
values of class attributes are assigned and changed. Here is the original
code url:
Here I am concerned is how attribute matrix.rows is changed. Through pdb
debugging, I can see in line 97, once "self.solut ions = set((val,))" is
executed, cell.row and matrix.rows will be updated. But I did not see any
assignment codes here. How could this change happen then? Thanks a lot!
John
# http://agolb.blogspot.com/2006/01/su...in-python.html
#!/usr/bin/env python
#
# sudoku-solver version 3
#
# Some ideas ripped-off from:
# http://www.linuxjournal.com/article/8729
# http://aspn.activestate.com/ASPN/Coo.../Recipe/440542
# Pavol solver in
#
#
# Copyright 2005 Ago,
# But you are free to copy, reuse, modify and distribute the code as you see
fit
from copy import deepcopy
class DeadEnd(Excepti on): pass
class Matrix:
def __init__(self, input):
self.rows = [[] for i in range(9)]
self.cols = [[] for i in range(9)]
self.submatrice s = [[] for i in range(9)]
self.cells = [Cell(i,self) for i in range(81)]
self.subdiagona ls = [self.rows[i][j+i%3] for i in range(9) for j in
[0,3,6]]
input = [s not in '-*' and int(s) or 0 for s in input if s in
'0123456789-*']
for cell,val in zip(self.cells, input):
if val: cell.setSolutio n(val)
def solve(self): #Brute-force solver
self.solveByRed uction()
lensols=[(len(c.solution s),c.index) for c in self.cells if not
c.solved]
if not lensols: return True
unsolved = min(lensols)[1]
solutions = list(self.cells[unsolved].solutions)
for s in solutions:
tmpmatrix = deepcopy(self)
try:
tmpmatrix.cells[unsolved].setSolution(s)
if tmpmatrix.solve ():
self.update(tmp matrix)
return True
except DeadEnd: pass
def solveByReductio n(self):
while True:
self.changed = False
for c in self.cells: c.solve()
for c in self.subdiagona ls: c.skim()
if not self.changed: break
def update(self, m):
self.rows, self.cols, self.submatrice s, self.cells,
self.subdiagona ls=\
m.rows, m.cols, m.submatrices, m.cells, m.subdiagonals
def __str__(self):
return "\n".join(s tr([c for c in row ])[1:-1] for row in self.rows)
class Cell:
def __init__(self, index, matrix):
self.solved = False
self.matrix = matrix
self.index = index
self.row = matrix.rows[index/9]
self.col = matrix.cols[index%9]
self.submatrix = matrix.submatri ces[((index/9)/3)*3+(index%9)/3]
self.row.append (self)
self.col.append (self)
self.submatrix. append(self)
self.solutions = set(range(1,10) )
def solve(self):
if self.solved: return
if len(self.soluti ons) == 1:
self.setSolutio n(self.solution s.pop())
else:
sol = set()
for cells in [self.row, self.col, self.submatrix]:
otherSolutions = self.cells2sols (cells, self)
sol |= (self.solutions - otherSolutions)
if len(sol) 1: raise DeadEnd()
if sol: self.setSolutio n(sol.pop())
def skim(self):
submatrix = set(self.submat rix)
for r in (set(self.row), set(self.col)):
subset1 = submatrix - r
subset2 = r - submatrix
solsNotIn1 = set(range(1,10) ) - self.cells2sols (subset2)
solsNotIn2 = set(range(1,10) ) - self.cells2sols (subset1)
for c in subset1: c.delSolutions( solsNotIn1)
for c in subset2: c.delSolutions( solsNotIn2)
def setSolution(sel f, val):
self.solved = True
self.solutions = set((val,))
self.matrix.cha nged = True
for other in self.row+self.c ol+self.submatr ix:
if other is self: continue
if other.solutions == self.solutions: raise DeadEnd()
other.delSoluti ons(self.soluti ons)
def delSolutions(se lf, val):
if not self.solved and val & self.solutions:
self.solutions -= val
self.matrix.cha nged = True
if not self.solutions: raise DeadEnd()
def __repr__(self):
return str(self.solved and list(self.solut ions)[0] or
list(self.solut ions))
@staticmethod
def cells2sols(cell s, exclude=None):
return set(s for c in cells for s in c.solutions if c is not
exclude)
if __name__ == "__main__":
input ='''
1,0,0,0,0,0,0,0 ,2
0,9,0,4,0,0,0,5 ,0
0,0,6,0,0,0,7,0 ,0
0,5,0,9,0,3,0,0 ,0
0,0,0,0,7,0,0,0 ,0
0,0,0,8,5,0,0,4 ,0
7,0,0,0,0,0,6,0 ,0
0,3,0,0,0,9,0,8 ,0
0,0,2,0,0,0,0,0 ,1
'''
matrix = Matrix(input)
matrix.solve()
print matrix