deepakkumarnd · October 26, 2023 09:24 · Oct 26, 2023
diff --git a/sudoku.py b/sudoku.py
@@ -0,0 +1,132 @@
+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)