Last active
August 29, 2024 13:45
-
-
Save 4ft35t/d284860ff96ddc4d7aae5a4262af907a to your computer and use it in GitHub Desktop.
Revisions
-
4ft35t revised this gist
Aug 29, 2024 . 1 changed file with 59 additions and 11 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -7,6 +7,7 @@ resolve sudoku ''' from copy import deepcopy class Cell: def __init__(self, x, y, value=None): @@ -58,31 +59,66 @@ def __init__(self, matrix): cell = Cell(x, y, value) self.cells.append(cell) def set_value_in_block(self): '''in a 3*3 block, if a number only in one cell's values, find and set it eg in matrix5: in the top center block, 5 only (3,2) cell's values, while this cell's values is [3,5,6] so set (3,2) cell's value to 5 ''' # 3*3 block for x in range(0, 9, 3): for y in range(0, 9, 3): block = [i for i in self.cells if i.x // 3 == x // 3 and i.y // 3 == y // 3] for n in range(1, 10): cells = [i for i in block if n in i.values] if len(cells) == 1: cell = cells[0] cell.values = [n] def resolve_with_backtrack(self): '''when no cell has only one value, use backtrack to resolve sudoku''' shortest = sorted([i for i in self.cells if i.values], key=lambda x: len(x.values))[0] current_state = deepcopy(self.cells) # try each value of cell cell = shortest for value in cell.values: new_sudoku = Sudoku([]) new_sudoku.cells = deepcopy(current_state) new_cell = [i for i in new_sudoku.cells if i.x == cell.x and i.y == cell.y][0] new_cell.values = [value] result = new_sudoku.resolve() if result: print('cell:', (cell.x, cell.y), 'value:', value, cell.values) return new_sudoku def resolve(self): while True: # set value for cells which has only one value in a 3*3 block self.set_value_in_block() count = 0 # set value for cells which has only one value for cell in self.cells: if len(cell.values) == 1: cell.set_value(self.cells) count += 1 # check if all cells have value, success if all([cell.value for cell in self.cells]): break # check if there is a cell which has no value, failed if any([not cell.value and not cell.values for cell in self.cells]): return [] # hard level, no cell has only one value # use backtrack to resolve if count == 0: result = self.resolve_with_backtrack() self.cells = result.cells return [[cell.value for cell in self.cells[i:i+9]] for i in range(0, 81, 9)] def show(self): @@ -145,7 +181,19 @@ def test(): [0, 0, 0, 0, 0, 0, 0, 0, 0] ] matrix5 = [ [0, 0, 6, 0, 8, 0, 5, 7, 0], [0, 0, 0, 4, 0, 0, 3, 0, 0], [0, 0, 0, 0, 2, 7, 1, 0, 0], [0, 7, 0, 0, 5, 0, 0, 4, 0], [0, 4, 9, 0, 0, 8, 6, 0, 0], [0, 0, 3, 0, 0, 0, 0, 1, 0], [0, 0, 0, 2, 3, 5, 9, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 9, 0, 0, 0, 2, 0] ] matrix_list = [matrix1, matrix2, matrix3, matrix4, matrix5] # matrix_list = [ matrix5] for matrix in matrix_list: print('matrix:') for row in matrix: -
Aug 7, 2024 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,160 @@ #!/usr/bin/env python3 # coding: utf-8 # @2024-07-25 22:54:41 # vim: set expandtab tabstop=4 shiftwidth=4 softtabstop=4: ''' resolve sudoku ''' class Cell: def __init__(self, x, y, value=None): self.x = x self.y = y self.init_value(value) def init_value(self, value): self.value = 0 if value: self.values = [value] else: # possible values of cell self.values = list(range(1, 10)) def get_near_cells(self, all_cells): ''' (0,0) ... (8,0) ... (0,8) ... (8,8) 9*9 cells ''' row = [i for i in all_cells if i.y == self.y] col = [i for i in all_cells if i.x == self.x] block = [i for i in all_cells if i.x // 3 == self.x // 3 and i.y // 3 == self.y // 3] return row + col + block def del_near_value(self, all_cells): '''delete current cell value from near cells''' near_cells = self.get_near_cells(all_cells) for cell in near_cells: if self.value in cell.values: cell.values.remove(self.value) def set_value(self, all_cells): '''cell has only one value, set it''' value = self.values[0] self.value = value self.values = [] # del value from near cells self.del_near_value(all_cells) class Sudoku: def __init__(self, matrix): self.cells = [] for y, row in enumerate(matrix): for x, value in enumerate(row): cell = Cell(x, y, value) self.cells.append(cell) def resolve(self): while True: count = 0 # set value for cells which has only one value for cell in self.cells: if len(cell.values) == 1: cell.set_value(self.cells) count += 1 # hard level, no cell has only one value # set shortest values of cell by the first value if count == 0: shortest = sorted([i for i in self.cells if i.values], key=lambda x: len(x.values))[0] # print('shortest:', shortest.x, shortest.y, shortest.values) shortest.values = shortest.values[:1] index = self.cells.index(shortest) self.cells[index] = shortest # check if all cells have value, success if all([cell.value for cell in self.cells]): break # check if there is a cell which has no value, failed if any([not cell.value and not cell.values for cell in self.cells]): print('unsolvable') return [] return [[cell.value for cell in self.cells[i:i+9]] for i in range(0, 81, 9)] def show(self): print('-' * 23) for i, cell in enumerate(self.cells): print(cell.value, end=' ') if i % 3 == 2: print('|', end=' ') if i % 9 == 8: print() if i % 27 == 26: print('-' * 23) def test(): matrix1 = [ [0, 6, 1, 0, 0, 4, 7, 0, 0], [0, 0, 9, 0, 0, 0, 6, 0, 0], [0, 0, 8, 0, 1, 0, 0, 9, 0], [0, 0, 7, 0, 2, 0, 3, 8, 0], [0, 0, 0, 8, 3, 9, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 3, 7, 0, 0, 0, 6], [0, 2, 0, 1, 0, 5, 8, 3, 0], [0, 0, 0, 0, 8, 0, 2, 0, 0] ] matrix2 = [ [0, 0, 0, 0, 0, 0, 4, 5, 6], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 5, 0, 0, 4, 6, 0, 9, 2], [2, 8, 0, 7, 0, 0, 0, 0, 3], [6, 0, 0, 0, 1, 0, 5, 0, 0], [0, 0, 0, 0, 0, 8, 0, 0, 0], [0, 0, 0, 0, 0, 0, 3, 0, 0], [8, 0, 0, 9, 0, 4, 6, 0, 0], [0, 2, 0, 8, 0, 0, 0, 0, 1] ] matrix3 = [ [0, 0, 0, 0, 0, 0, 0, 1, 2], [0, 0, 0, 0, 3, 5, 0, 0, 0], [0, 0, 0, 6, 0, 0, 0, 7, 0], [7, 0, 0, 0, 0, 0, 3, 0, 0], [0, 0, 0, 4, 0, 0, 8, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 2, 0, 0, 0, 0], [0, 8, 0, 0, 0, 0, 0, 4, 0], [0, 5, 0, 0, 0, 0, 6, 0, 0] ] matrix4 = [ [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 8, 0, 0, 0, 0, 4, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 6, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [2, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 2, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0] ] matrix_list = [matrix1, matrix2, matrix3, matrix4] for matrix in matrix_list: print('matrix:') for row in matrix: print(row) print('result:') sudoku = Sudoku(matrix) result = sudoku.resolve() if result: sudoku.show() if __name__ == '__main__': test()