''' Sudoku Solver
    Andrew Henshaw'''

 from numarray import array

 class ConsistencyError(Exception): pass
 class BoardSolved(Exception): pass

 class Board:
    def __init__(self, board=None):
        if board is not None:
            self.board = board.copy()
    
    def InitFromString(self, boardstring):
        s = boardstring.replace('\n', '').replace(' ','').replace('-','0').replace('_','0')
        self.board = array([int(x) for x in s]).resize((9, 9))
        
    def IsValid(self, r, c, value):
        # row check, column check, 3x3 check
        if (value in self.board[r]) or (value in self.board[:,c]): 
            return False
        r = (r // 3) * 3
        c = (c // 3) * 3
        return value not in self.board[r:r+3, c:c+3].flat
    
    def GetPossibles(self, r, c):
        possibles = [x for x in range(1, 10) if self.IsValid(r, c, x)]
        if not possibles:
            raise ConsistencyError
        if len(possibles) == 1:
            self.board[r,c] = possibles[0]
            return True            
        return possibles
        
    def Simplify(self):
        self.potentials = {}
        for r in range(9):
            for c in range(9):
                if not self.board[r, c]:
                    self.solved = False
                    result = self.GetPossibles(r, c)
                    if result is True:
                        return True
                    else:
                        self.potentials[(r,c)] = result
        
    def _solve(self, level):
        occupied = len(self.board.flat.nonzero()[0])
        while self.Simplify(): 
            pass
        deduced = len(self.board.flat.nonzero()[0]) - occupied
        if deduced:
            print '  '*level, 'deduced %d cells' % deduced
        if 0 not in self.board.flat:
            raise BoardSolved, self.board
    
        # start testing guesses
        row, col = self.potentials.keys()[0]
        for value in self.potentials[(row, col)]:
            print '  '*level, 'trying %d at (%d, %d)' % (value, row, col, )
            self.board[row, col] = value
            testboard = Board(self.board)
            try:
                testboard._solve(level+1)
            except ConsistencyError:
                continue

    def Solve(self):
        print "Here's the starting point:\n", self.board
        print "\nTrying to solve it now ..."
        try:
            self._solve(1)
        except BoardSolved, board:
            print "done.\n\nHere's my solution:\n", board

 if __name__ == '__main__':
    import sys
    puzzle = open(sys.argv[1]).read()
    b = Board()
    b.InitFromString(puzzle)
    b.Solve()