開発環境
- macOS Mojave - Apple (OS)
- Emacs (Text Editor)
- Windows 10 Pro (OS)
- Visual Studio Code (Text Editor)
- Python 3.7 (プログラミング言語)
問題解決のPythonプログラミング ―数学パズルで鍛えるアルゴリズム的思考 (Srini Devadas (著)、黒川 利明 (翻訳)、オライリージャパン)の14章(数独は二度とごめんだ)、練習問題(パズル問題2)を取り組んでみる。
コード(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:
return x, y
return -1, -1
def is_valid(grid: list, i: int, j: int, e: int) -> bool:
if i == j and not all([e != grid[x][x] for x in range(9)]):
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]]
grid[i][j] = e
implications = [(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:
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]
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):
grid[x0][y0] = val
implications.append((x0, y0, val))
if len(implications) == implications_len:
break
implications_len = len(implications)
return implications
def undo_implications(grid: int, implications: list) -> None:
for x, y, _ in implications:
grid[x][y] = 0
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__':
backtracks = 0
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]],
[[1, 0, 5, 7, 0, 2, 6, 3, 8],
[2, 0, 0, 0, 0, 6, 0, 0, 5],
[0, 6, 3, 8, 4, 0, 2, 1, 0],
[0, 5, 9, 2, 0, 1, 3, 8, 0],
[0, 0, 2, 0, 5, 8, 0, 0, 9],
[7, 1, 0, 0, 3, 0, 5, 0, 2],
[0, 0, 4, 5, 6, 0, 7, 2, 0],
[5, 0, 0, 0, 0, 4, 0, 6, 3],
[3, 2, 6, 1, 0, 7, 0, 0, 4]]
]
for input0 in inputs:
print_sudoku(input0)
if solve_sudoku(input0):
print_sudoku(input0)
else:
print('no solution')
print()
入出力結果(Terminal, cmd(コマンドプロンプト), Jupyter(IPython))
$ ./sample2.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] ----------------------------- no solution ----------------------------- [1, 0, 5] [7, 0, 2] [6, 3, 8] [2, 0, 0] [0, 0, 6] [0, 0, 5] [0, 6, 3] [8, 4, 0] [2, 1, 0] [0, 5, 9] [2, 0, 1] [3, 8, 0] [0, 0, 2] [0, 5, 8] [0, 0, 9] [7, 1, 0] [0, 3, 0] [5, 0, 2] [0, 0, 4] [5, 6, 0] [7, 2, 0] [5, 0, 0] [0, 0, 4] [0, 6, 3] [3, 2, 6] [1, 0, 7] [0, 0, 4] ----------------------------- ----------------------------- [1, 4, 5] [7, 9, 2] [6, 3, 8] [2, 8, 7] [3, 1, 6] [4, 9, 5] [9, 6, 3] [8, 4, 5] [2, 1, 7] [4, 5, 9] [2, 7, 1] [3, 8, 6] [6, 3, 2] [4, 5, 8] [1, 7, 9] [7, 1, 8] [6, 3, 9] [5, 4, 2] [8, 9, 4] [5, 6, 3] [7, 2, 1] [5, 7, 1] [9, 2, 4] [8, 6, 3] [3, 2, 6] [1, 8, 7] [9, 5, 4] ----------------------------- $
0 コメント:
コメントを投稿