#!/usr/bin/python import os import sys class Cell: def __init__(self, callback): self.callback = callback # all possibilities are allowed at this point self.contents = range(1, 10) def set(self, value): assert not self.solved() self.contents = [ value ] self.callback(self) def remove(self, value): assert not self.solved() or value != self.value() try: self.contents.remove(value) if self.solved(): self.callback(self) except ValueError: pass def solved(self): return len(self.contents) == 1 def value(self): assert self.solved() return self.contents[0] class Group: def __init__(self, cells): self.cells = cells def clean(self, cell): "The cell has been solved, clean its value from this group's cells." if cell not in self.cells: return value = cell.value() for scan in self.cells: if scan is not cell: scan.remove(value) def one_spot(self): "Is there one spot where a number can go? If yes, then put it there." while True: for value in range(1, 10): pos = -1 for i in range(9): if value in self.cells[i].contents: if pos >= 0: break pos = i else: # we didn't break out. thus, we found the number in just one # position in this group (it has to be somewhere). let's solve # that cell if it hasn't been solved yet. cell = self.cells[pos] if not cell.solved(): cell.set(value) # break out of the value loop and start again. break else: # we didn't break out of the for loop, so we didn't solve any # cells in this group. we're done return def locate(self, value): "Is there a cell that is solved as ?" for i in range(9): cell = self.cells[i] if value in cell.contents: if cell.solved(): return i return -1 # NOTREACHED assert False def place(self, value, idx1, idx2): if min(idx1, idx2) < 3: if max(idx1, idx2) < 6: subset = self.cells[6:] else: subset = self.cells[3:6] else: subset = self.cells[6:] class Puzzle: def __init__(self): self.cells = [ Cell(self.notify) for i in range(81) ] self.rows = [ Group([ self.cells[i + j] for j in range(9) ]) for i in range(0, 81, 9) ] self.cols = [ Group([ self.cells[i + j] for j in range(0, 81, 9) ]) for i in range(9) ] self.groups = [ Group([ self.cells[i + j] for j in (0, 1, 2, 9, 10, 11, 18, 19, 20) ]) for i in (0, 3, 6, 27, 30, 33, 54, 57, 60) ] def notify(self, cell): "Notification that the given cell has been solved." for group in self.rows + self.cols + self.groups: group.clean(cell) def set(self, row, col, value): cell = self.cells[row*9 + col] if not cell.solved(): cell.set(value) else: assert cell.value() == value def solved(self): for cell in self.cells: if not cell.solved(): return False return True def analyze(self): # are there any groups where we can force a number into place? for group in self.rows + self.cols + self.groups: group.one_spot() return for value in range(1, 10): self.resolve3(self.rows[:3], value) self.resolve3(self.rows[3:6], value) self.resolve3(self.rows[6:], value) self.resolve3(self.cols[:3], value) self.resolve3(self.cols[3:6], value) self.resolve3(self.cols[6:], value) def resolve3(self, (g1, g2, g3), value): i1 = g1.locate(value) i2 = g2.locate(value) i3 = g3.locate(value) if i1 >= 0: if i2 >= 0: g3.place(value, i1, i2) elif i3 >= 0: g2.place(value, i1, i3) elif i2 >= 0 and i3 >= 0: g1.place(value, i2, i3) def print_detailed(self): for row in self.rows: for i in (1, 4, 7): out = [ ] for cell in row.cells: if cell.solved(): if i == 4: out.append(' %d ' % cell.value()) else: out.append(' ') else: out.append(''.join([i+j in cell.contents and str(i+j) or '.' for j in range(3)])) print ' '.join(out) def __str__(self): rows = [ ' '.join([cell.solved() and str(cell.value()) or ' ' for cell in row.cells]) for row in self.rows ] return '\n'.join(rows) def main(): puzzle = Puzzle() while not puzzle.solved(): print puzzle if os.isatty(0): line = raw_input('row,col,value: ') else: print line = sys.stdin.readline() if not line.strip(): puzzle.print_detailed() sys.exit(1) puzzle.set(*map(int, line.split())) puzzle.analyze() print puzzle if __name__ == '__main__': main()