2018年12月22日土曜日

開発環境

問題解決の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 コメント:

コメントを投稿