from texttable import Texttable


class Sudoku:
    __board: list[list[int]]
    __is_solved: bool

    def __init__(self, grid: list[list[int]]):
        self.__board = grid
        self.__is_solved = False

    @staticmethod
    def from_line(input_line: str):
        if not ((len(input_line) == 81) and input_line.isdigit()):
            raise Exception("Invalid sudoku puzzle")
        grid = []

        for i in range(0, 80, 9):
            grid.append([*input_line[i:i + 9]])

        return Sudoku(grid)

    def __str__(self):
        t = Texttable()
        grid = []
        for row in self.__board:
            new_row = []
            for col in row:
                if col == "0":
                    new_row.append(" ")
                else:
                    new_row.append(str(col))
            grid.append(new_row)

        t.add_rows(grid, header=None)
        return t.draw()

    def __exists_in_same_row(self, value, row_index):
        current_row = self.__board[row_index]
        return str(value) in current_row

    def __exists_in_same_column(self, value, col_index):
        current_column = []

        for i in range(0, 9):
            current_column.append(self.__board[i][col_index])

        return str(value) in current_column

    def __exists_in_same_subgrid(self, value, row, col):
        base_x = 3 * int(row / 3)
        base_y = 3 * int(col / 3)
        subgrid_values = []

        for i in range(0, 3):
            for j in range(0, 3):
                subgrid_values.append(self.__board[base_x + i][base_y + j])
        return str(value) in subgrid_values

    def __is_valid_rows(self):
        for row in self.__board:
            for n in range(1, 10):
                if not (str(n) in row):
                    return False

        return True

    def __is_valid_columns(self):
        for j in range(0, 9):
            column = []

            for i in range(0, 9):
                column.append(self.__board[i][j])

            for n in range(1, 10):
                if not (str(n) in column):
                    return False
        return True

    def __is_valid_3x3_grids(self):
        for x in range(0, 3):
            for y in range(0, 3):
                sub_grid = []

                for i in range(0, 3):
                    for j in range(0, 3):
                        sub_grid.append(self.__board[3 * x + i][3 * y + j])

                for n in range(1, 10):
                    if not (str(n) in sub_grid):
                        return False

        return True

    def is_solved(self):
        if not self.__is_solved:
            self.__is_solved = self.__is_valid_rows() and self.__is_valid_columns() and self.__is_valid_3x3_grids()

        return self.__is_solved

    def solve(self):
        if self.is_solved():
            return

        for i in range(0, 9):
            for j in range(0, 9):
                if self.__board[i][j] == "0":
                    for try_value in range(1, 10):
                        if (self.__exists_in_same_row(try_value, i) or
                                self.__exists_in_same_column(try_value, j) or
                                self.__exists_in_same_subgrid(try_value, i, j)):
                            continue
                        else:
                            self.__board[i][j] = str(try_value)
                            self.solve()

                            if self.is_solved():
                                return;
                            else:
                                self.__board[i][j] = "0"

                if self.__board[i][j] == "0":  # solution does not exists in this route
                    return


if __name__ == '__main__':
    sudoku = Sudoku.from_line(
        "580403010600050394034000050340019000000567483000040000050000030010070000002130800")
    print(sudoku)
    sudoku.solve()
    print("Solution")
    print(sudoku)