開発環境
- macOS Mojave - Apple (OS)
- Emacs (Text Editor)
- Windows 10 Pro (OS)
- Visual Studio Code (Text Editor)
- Python 3.7 (プログラミング言語)
問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の14章(数独は二度とごめんだ)、練習問題(パズル問題3)を取り組んでみる。
コード(Emacs)
Python 3
#!/usr/bin/env python3 def find_next_cell_to_fill(grid: list) -> (int, int): for x in range(9): for y in range(9): if grid[x][y] == 0 or grid[x][y] == -2: return x, y return -1, -1 def is_valid(grid: list, i: int, j: int, e: int) -> bool: if grid[i][j] == -2 and e % 2 != 0: return False if all([e != grid[i][y] for y in range(9)]) and \ all([e != grid[x][j] for x in range(9)]): top_x = 3 * (i // 3) top_y = 3 * (j // 3) for x in range(top_x, top_x + 3): for y in range(top_y, top_y + 3): if grid[x][y] == e: return False return True return False def make_implications(grid: list, i: int, j: int, e: int) -> list: sectors = [[0, 3, 0, 3], [3, 6, 0, 3], [6, 9, 0, 3], [0, 3, 3, 6], [3, 6, 3, 6], [6, 9, 3, 6], [0, 3, 6, 9], [3, 6, 6, 9], [6, 9, 6, 9]] implications = [(i, j, e, grid[i][j])] grid[i][j] = e implications_len = len(implications) while True: for x1, x2, y1, y2 in sectors: val_set = set(range(1, 10)) for x in range(x1, x2): for y in range(y1, y2): if grid[x][y] != 0 and grid[x][y] != -2: val_set.remove(grid[x][y]) sector_infos = [[x, y, val_set.copy()] for x in range(x1, x2) for y in range(y1, y2) if grid[x][y] == 0 or grid[x][y] == -2] for x0, y0, val_set0 in sector_infos: row_val = {grid[x0][y] for y in range(9)} left = val_set0 - row_val col_val = {grid[x][y0] for x in range(9)} left -= col_val if len(left) == 1: val = left.pop() if is_valid(grid, x0, y0, val): val_before = grid[x0][y0] grid[x0][y0] = val implications.append((x0, y0, val, val_before)) if len(implications) == implications_len: break implications_len = len(implications) return implications def undo_implications(grid: int, implications: list) -> None: for x, y, _, val in implications: grid[x][y] = val backtracks = 0 def solve_sudoku(grid: list, i: int = 0, j: int = 0) -> bool: global backtracks i, j = find_next_cell_to_fill(grid) if i == -1: return True for e in range(1, 10): if is_valid(grid, i, j, e): implications = make_implications(grid, i, j, e) if solve_sudoku(grid, i, j): return True backtracks += 1 undo_implications(grid, implications) return False def print_sudoku(grid: list) -> None: print('-' * 29) for i, row in enumerate(grid): if i % 3 == 0 and i != 0: print(' ') print(f'{row[0:3]} {row[3:6]} {row[6:9]}') print('-' * 29) if __name__ == '__main__': inputs = [[[5, 1, 7, 6, 0, 0, 0, 3, 4], [0, 8, 9, 0, 0, 4, 0, 0, 0], [3, 0, 6, 2, 0, 5, 0, 9, 0], [6, 0, 0, 0, 0, 0, 0, 1, 0], [0, 3, 0, 0, 0, 6, 0, 4, 7], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 9, 0, 0, 0, 0, 0, 7, 8], [7, 0, 3, 4, 0, 0, 5, 6, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]], [[8, 4, 0, 0, 5, 0, -2, 0, 0], [3, 0, 0, 6, 0, 8, 0, 4, 0], [0, 0, -2, 4, 0, 9, 0, 0, -2], [0, 2, 3, 0, -2, 0, 9, 8, 0], [1, 0, 0, -2, 0, -2, 0, 0, 4], [0, 9, 8, 0, -2, 0, 1, 6, 0], [-2, 0, 0, 5, 0, 3, -2, 0, 0], [0, 3, 0, 1, 0, 6, 0, 0, 7], [0, 0, -2, 0, 2, 0, 0, 1, 3]], [[0 for _ in range(9)] for _ in range(9)], [[-2 for _ in range(9)] for _ in range(9)]] for input0 in inputs: backtracks = 0 print_sudoku(input0) if solve_sudoku(input0): print_sudoku(input0) else: print('no solution') print(f'backtracks: {backtracks}')
入出力結果(Terminal, cmd(コマンドプロンプト), Jupyter(IPython))
$ ./sample3.py ----------------------------- [5, 1, 7] [6, 0, 0] [0, 3, 4] [0, 8, 9] [0, 0, 4] [0, 0, 0] [3, 0, 6] [2, 0, 5] [0, 9, 0] [6, 0, 0] [0, 0, 0] [0, 1, 0] [0, 3, 0] [0, 0, 6] [0, 4, 7] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 9, 0] [0, 0, 0] [0, 7, 8] [7, 0, 3] [4, 0, 0] [5, 6, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] ----------------------------- ----------------------------- [5, 1, 7] [6, 9, 8] [2, 3, 4] [2, 8, 9] [1, 3, 4] [7, 5, 6] [3, 4, 6] [2, 7, 5] [8, 9, 1] [6, 7, 2] [8, 4, 9] [3, 1, 5] [1, 3, 8] [5, 2, 6] [9, 4, 7] [9, 5, 4] [7, 1, 3] [6, 8, 2] [4, 9, 5] [3, 6, 2] [1, 7, 8] [7, 2, 3] [4, 8, 1] [5, 6, 9] [8, 6, 1] [9, 5, 7] [4, 2, 3] ----------------------------- backtracks: 2 ----------------------------- [8, 4, 0] [0, 5, 0] [-2, 0, 0] [3, 0, 0] [6, 0, 8] [0, 4, 0] [0, 0, -2] [4, 0, 9] [0, 0, -2] [0, 2, 3] [0, -2, 0] [9, 8, 0] [1, 0, 0] [-2, 0, -2] [0, 0, 4] [0, 9, 8] [0, -2, 0] [1, 6, 0] [-2, 0, 0] [5, 0, 3] [-2, 0, 0] [0, 3, 0] [1, 0, 6] [0, 0, 7] [0, 0, -2] [0, 2, 0] [0, 1, 3] ----------------------------- ----------------------------- [8, 4, 9] [2, 5, 7] [6, 3, 1] [3, 5, 7] [6, 1, 8] [2, 4, 9] [6, 1, 2] [4, 3, 9] [7, 5, 8] [4, 2, 3] [7, 6, 1] [9, 8, 5] [1, 6, 5] [8, 9, 2] [3, 7, 4] [7, 9, 8] [3, 4, 5] [1, 6, 2] [2, 8, 1] [5, 7, 3] [4, 9, 6] [9, 3, 4] [1, 8, 6] [5, 2, 7] [5, 7, 6] [9, 2, 4] [8, 1, 3] ----------------------------- backtracks: 25 ----------------------------- [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] [0, 0, 0] ----------------------------- ----------------------------- [1, 2, 3] [4, 5, 6] [7, 8, 9] [4, 5, 6] [7, 8, 9] [1, 2, 3] [7, 8, 9] [1, 2, 3] [4, 5, 6] [2, 1, 4] [3, 6, 5] [8, 9, 7] [3, 6, 5] [8, 9, 7] [2, 1, 4] [8, 9, 7] [2, 1, 4] [3, 6, 5] [5, 3, 1] [6, 4, 2] [9, 7, 8] [6, 4, 2] [9, 7, 8] [5, 3, 1] [9, 7, 8] [5, 3, 1] [6, 4, 2] ----------------------------- backtracks: 151 ----------------------------- [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] [-2, -2, -2] ----------------------------- no solution backtracks: 64 $
0 コメント:
コメントを投稿