sudoku.py

class BacktrackingSolver:
    def solve(self, state):
        if self.is_a_solution(state):
            return state

        for move in self.get_candidates(state):
            self.make_move(move, state)
            solution = self.solve(state)
            if solution:
                return solution
            else:
                self.unmake_move(move, state)

        return None

    def is_a_solution(self, state):
        raise NotImplemented

    def get_candidates(self, state):
        raise NotImplemented

    def make_move(self, move, state):
        raise NotImplemented

    def unmake_move(self, move, state):
        raise NotImplemented


class BacktrackingSudokuSolver(BacktrackingSolver):
    def is_a_solution(self, board):
        return board.full

    def get_candidates(self, board):
        possible_moves = board.possible_moves()
        if any(len(values) == 0 for x, y, values in possible_moves):
            # If there's a square with no possible moves, stop exploring this branch
            return []
        else:
            x, y, values = min(possible_moves, key=lambda (x, y, values): len(values))
            return [(x, y, value) for value in values]

    def make_move(self, move, board):
        x, y, value = move
        board.set_value(x, y, value)

    def unmake_move(self, move, board):
        x, y, value = move
        board.set_value(x, y, None)


class SudokuBoard:
    def __init__(self, board):
        self.board = board

    def set_value(self, x, y, value):
        self.board[y][x] = value

    @property
    def full(self):
        return all(v is not None for l in self.board for v in l)

    @property
    def empty_squares(self):
        return (
            (x, y) for x in range(9) for y in range(9)
            if self.board[y][x] is None
        )

    def moves_for_square(self, x, y):
        row_values = set(self.board[y])
        column_values = set(self.board[j][x] for j in range(9))
        square_values = set(
            self.board[j][i]
            for i in range(x // 3 * 3, x // 3 * 3 + 3)
            for j in range(y // 3 * 3, y // 3 * 3 + 3)
        )
        return {1, 2, 3, 4, 5, 6, 7, 8, 9} - (row_values | column_values | square_values)

    def possible_moves(self):
        """
        Return a generator of possible move tuples of the form (x, y, values)
        e.g: (3, 5, {1, 5, 9})
        """
        return [(x, y, self.moves_for_square(x, y)) for x, y in self.empty_squares]

    def __str__(self):
        string = ""
        for y in range(9):
            if y % 3 == 0:
                string += '+---+---+---+\n'
            for x, value in enumerate(self.board[y]):
                if x % 3 == 0:
                    string += '|'
                string += str(value) if value is not None else ' '
            string += '|\n'

        string += '+---+---+---+\n'
        return string

    def __eq__(self, other):
        return self.board == other.board


def test():
    board = SudokuBoard([
        [None, None, None, None, None, None, None, 1, 2],
        [None, None, None, None, 3, 5, None, None, None],
        [None, None, None, 6, None, None, None, 7, None],
        [7, None, None, None, None, None, 3, None, None],
        [None, None, None, 4, None, None, 8, None, None],
        [1, None, None, None, None, None, None, None, None],
        [None, None, None, 1, 2, None, None, None, None],
        [None, 8, None, None, None, None, None, 4, None],
        [None, 5, None, None, None, None, 6, None, None],
    ])
    expected = SudokuBoard([
        [6, 7, 3, 8, 9, 4, 5, 1, 2],
        [9, 1, 2, 7, 3, 5, 4, 8, 6],
        [8, 4, 5, 6, 1, 2, 9, 7, 3],
        [7, 9, 8, 2, 6, 1, 3, 5, 4],
        [5, 2, 6, 4, 7, 3, 8, 9, 1],
        [1, 3, 4, 5, 8, 9, 2, 6, 7],
        [4, 6, 9, 1, 2, 8, 7, 3, 5],
        [2, 8, 7, 3, 5, 6, 1, 4, 9],
        [3, 5, 1, 9, 4, 7, 6, 2, 8],
    ])
    solution = BacktrackingSudokuSolver().solve(board)
    assert solution == expected


if __name__ == '__main__':
    test()