class Board:
    WIDTH = 9
    HEIGHT = 9

    def __init__(self):
        self.squares = [
            [5, 3, None, None, 7, None, None, None, None],
            [6, None, None, 1, 9, 5, None, None, None],
            [None, 9, 8, None, None, None, None, 6, None],
            [8, None, None, None, 6, None, None, None, 3],
            [4, None, None, 8, None, 3, None, None, 1],
            [7, None, None, None, 2, None, None, None, 6],
            [None, 6, None, None, None, None, 2, 8, None],
            [None, None, None, 4, 1, 9, None, None, 5],
            [None, None, None, None, 8, None, None, 7, 9]
        ]

    def display(self):
        for row in self.squares:
            print([(val if val is not None else '?') for val in row])

    def row_vals(self, x, y):
        return {val for val in self.squares[y] if val is not None}

    def col_vals(self, x, y):
        return {row[x] for row in self.squares if row[x] is not None}

    def sqr_vals(self, x, y):
        x = (x // 3) * 3
        y = (y // 3) * 3

        return {
            self.squares[j][i] for j in range(y, y+3) for i in range(x, x+3)
            if self.squares[j][i] is not None
        }


class Solver():
    POSSIBLE = {1, 2, 3, 4, 5, 6, 7, 8, 9}

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

    def constrain(self):
        for y in range(self.board.HEIGHT):
            for x in range(self.board.WIDTH):
                if self.board.squares[y][x] is not None:
                    continue

                row_possible = self.POSSIBLE - self.board.row_vals(x, y)
                col_possible = self.POSSIBLE - self.board.col_vals(x, y)
                sqr_possible = self.POSSIBLE - self.board.sqr_vals(x, y)
                possible = row_possible & col_possible & sqr_possible

                if len(possible) == 1:
                    self.board.squares[y][x] = possible.pop()

    def complete(self):
        for y in range(self.board.HEIGHT):
            for x in range(self.board.WIDTH):
                if self.board.squares[y][x] is None:
                    return False

        return True


if __name__ == '__main__':
    board = Board()
    solver = Solver(board)

    while not solver.complete():
        solver.constrain()

    board.display()