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: http://agolb.blogspot.com/2006/01/sudoku-solver-in-python.html Here I am concerned is how attribute matrix.rows is changed. Through pdb debugging, I can see in line 97, once "self.solutions = 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/sudoku-solver-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/Cookbook/Python/Recipe/440542 # Pavol solver in # http://groups.google.com/group/comp.lang.python/browse_thread/thread/5087890f4c5e770d # # 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(Exception): pass class Matrix: def __init__(self, input): self.rows = [[] for i in range(9)] self.cols = [[] for i in range(9)] self.submatrices = [[] for i in range(9)] self.cells = [Cell(i,self) for i in range(81)] self.subdiagonals = [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.setSolution(val) def solve(self): #Brute-force solver self.solveByReduction() lensols=[(len(c.solutions),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(tmpmatrix) return True except DeadEnd: pass def solveByReduction(self): while True: self.changed = False for c in self.cells: c.solve() for c in self.subdiagonals: c.skim() if not self.changed: break def update(self, m): self.rows, self.cols, self.submatrices, self.cells, self.subdiagonals=\ m.rows, m.cols, m.submatrices, m.cells, m.subdiagonals def __str__(self): return "\n".join(str([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.submatrices[((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.solutions) == 1: self.setSolution(self.solutions.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.setSolution(sol.pop()) def skim(self): submatrix = set(self.submatrix) 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(self, val): self.solved = True self.solutions = set((val,)) self.matrix.changed = True for other in self.row+self.col+self.submatrix: if other is self: continue if other.solutions == self.solutions: raise DeadEnd() other.delSolutions(self.solutions) def delSolutions(self, val): if not self.solved and val & self.solutions: self.solutions -= val self.matrix.changed = True if not self.solutions: raise DeadEnd() def __repr__(self): return str(self.solved and list(self.solutions)[0] or list(self.solutions)) @staticmethod def cells2sols(cells, 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
# http://agolb.blogspot.com/2006/01/sudoku-solver-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/Cookbook/Python/Recipe/440542 # Pavol solver in # http://groups.google.com/group/comp.lang.python/browse_thread/thread/5087890f4c5e770d # # 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(Exception): pass class Matrix: def __init__(self, input): self.rows = [[] for i in range(9)] self.cols = [[] for i in range(9)] self.submatrices = [[] for i in range(9)] self.cells = [Cell(i,self) for i in range(81)] self.subdiagonals = [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.setSolution(val) def solve(self): #Brute-force solver self.solveByReduction() lensols=[(len(c.solutions),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(tmpmatrix) return True except DeadEnd: pass def solveByReduction(self): while True: self.changed = False for c in self.cells: c.solve() for c in self.subdiagonals: c.skim() if not self.changed: break def update(self, m): self.rows, self.cols, self.submatrices, self.cells, self.subdiagonals=\ m.rows, m.cols, m.submatrices, m.cells, m.subdiagonals def __str__(self): return "\n".join(str([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.submatrices[((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.solutions) == 1: self.setSolution(self.solutions.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.setSolution(sol.pop()) def skim(self): submatrix = set(self.submatrix) 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(self, val): self.solved = True self.solutions = set((val,)) self.matrix.changed = True for other in self.row+self.col+self.submatrix: if other is self: continue if other.solutions == self.solutions: raise DeadEnd() other.delSolutions(self.solutions) def delSolutions(self, val): if not self.solved and val & self.solutions: self.solutions -= val self.matrix.changed = True if not self.solutions: raise DeadEnd() def __repr__(self): return str(self.solved and list(self.solutions)[0] or list(self.solutions)) @staticmethod def cells2sols(cells, 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
-- http://mail.python.org/mailman/listinfo/python-list
