class Board:
    symbols = "123456789"
    blank = "."

    _board = ["." * 10 for i in range(9)]

    def set_initial(self, board: list):
        self._board = board.copy()

    def get_row(self, x):
        return self._board[x]

    def get_col(self, y):
        return "".join([r[y] for r in self._board])

    def get_block(self, x, y):
        row = x // 3
        col = y // 3
        return [r[col * 3 : (col + 1) * 3] for r in self._board[row * 3 : (row + 1) * 3]]

    def is_blank(self, x, y):
        return self._board[x][y] == self.blank

    def is_solved(self):
        return self.blank not in "".join(self._board)

    def set_cell(self, x, y, value):
        self._board[x] = self._board[x][:y] + value + self._board[x][y + 1 :]

    def get_possibilities(self, x, y):
        all_symbols = list(self.get_row(x) + self.get_col(y) + "".join(self.get_block(x, y)))
        return set(self.symbols).difference(all_symbols)

    def get_all_possibilities(self):
        return [[self.get_possibilities(i, j) for j in range(9)] for i in range(9)]

    def get_unique_cell(self):
        for i in range(9):
            for j in range(9):
                if self.is_blank(i, j) and len(self.get_possibilities(i, j)) == 1:
                    return (i, j)
        return None

    def get_next_blank(self):
        for i in range(9):
            for j in range(9):
                if self.is_blank(i, j):
                    return (i, j)

    def solve(self):
        while cell := self.get_unique_cell():
            x, y = cell
            value = self.get_possibilities(x, y).pop()
            # print(x, y)
            self.set_cell(x, y, value)
        if not self.is_solved():
            cell = self.get_next_blank()
            x, y = cell
            snapshot = self._board.copy()
            for value in self.get_possibilities(x, y):
                self.set_cell(x, y, value)
                self.solve()
                if self.is_solved():
                    break
                self.set_initial(snapshot)
        return self._board