Pythonで数独認識して解く③ (数独を解く)

初めに

• 前回(Pythonで数独認識して解く②) の続編です
• 数独を認識して解くプログラムを作る
• 文字認識まで完了した
• 今回は実際にPythonで数独を解く
• 数独はPythonで考えて解く話 をだいぶ参考にさせていただきました
• numpyを使い，行列演算を変更しただけです。

[環境]
・Python 3.7.3
・numpy 1.16.4

Sourse Code

• 入力number_detectionは数独の版を表す9×9のnumpy配列。空欄は0とする。

solve_sudoku.py

import numpy as np
"""
数独を解く
"""
input_grid = np.array([[0, 0, 0, 0, 2, 0, 3, 0, 6],
                       [0, 0, 0, 1, 8, 0, 9, 4, 0],
                       [3, 8, 0, 0, 4, 5, 1, 0, 7],
                       [9, 0, 4, 8, 0, 2, 0, 0, 0],
                       [1, 2, 0, 0, 3, 4, 7, 0, 8],
                       [0, 0, 0, 9, 6, 0, 2, 1, 0],
                       [2, 4, 0, 0, 7, 8, 5, 0, 9],
                       [8, 0, 3, 2, 0, 6, 0, 0, 0],
                       [6, 5, 0, 0, 0, 1, 0, 0, 0]],dtype=np.int)
count = 0

print("First : ")
print(input_grid,"\n")

def find_zero_cell(grid):
    for y in range(9):
        for x in range(9):
            if grid[y,x] == 0:
                # 0 の座標を返す
                return y, x
    # すべてのマスに数字が入っている状態
    return -1, -1

def valid_check(grid, y, x, num):
    # 行，列での重複確認
    row = num not in grid[y]
    col = num not in input_grid[:,x]
    # ブロックでの重複確認
    block_x, block_y = (x//3)*3, (y//3)*3
    block_grid = input_grid[block_y:block_y+3,block_x:block_x+3]
    block = num not in block_grid.flatten()
    # 重複check
    return all([row, col, block])

def solve_sudoku(grid, y=0, x=0):
    global count
    y, x = find_zero_cell(grid)
    # 0のセルがなくなったら終了
    if y == -1 or x == -1:
        return True
    # 入力
    for num in range(1, 10):
        if valid_check(grid, y, x, num):
            grid[y,x] = num
            if solve_sudoku(grid, y, x):
                return True
            count += 1
            grid[y,x] = 0
    return False

if solve_sudoku(input_grid):
    print(input_grid)
    print("count :",count)

解説

• 参考にさせていただいたサイトのプログラムから大きく変わっていないので簡単な解説のみとします。

関数 find_zero_cell

• 現在のグリッド全体から空欄のセル(0が格納されているセル)を探す関数。
• 左上から順に探しているだけなので効率は良くない可能性大。

関数 valid_check

• find_zero_cell関数で見つけた空白のセルに1から小さい順に数字を入れていく。
• 入れた数字が縦横，ブロック(3×3)で 重複が無いかをチェックする関数。
• 重複が無ければTrue，重複があればFalseを返す。
• この部分の記述はがnumpy配列のスライスによって簡単に書けたと思われる。

関数 solve_sudoku

• メインの関数。
• 再帰を行っている。(このため遅い)
• find_zero_cell関数で空白を探し，
• 空白のセルに1から数字を入れてvalid_check関数を呼び，
• Trueが返ってくれば次のセルに移動(ここで再帰する)
• find_zero_cell関数で空白がなくなったと判定されたときにsolve_sudoku関数はTrueを返す
• 再帰の回数をcountに格納(必要であれば)

実行結果

PS C:\Users\~~~~\python> python .\solve_sudoku.py
First :
[[0 0 0 0 2 0 3 0 6]
 [0 0 0 1 8 0 9 4 0]
 [3 8 0 0 4 5 1 0 7]
 [9 0 4 8 0 2 0 0 0]
 [1 2 0 0 3 4 7 0 8]
 [0 0 0 9 6 0 2 1 0]
 [2 4 0 0 7 8 5 0 9]
 [8 0 3 2 0 6 0 0 0]
 [6 5 0 0 0 1 0 0 0]]

[[4 1 5 7 2 9 3 8 6]
 [7 6 2 1 8 3 9 4 5]
 [3 8 9 6 4 5 1 2 7]
 [9 7 4 8 1 2 6 5 3]
 [1 2 6 5 3 4 7 9 8]
 [5 3 8 9 6 7 2 1 4]
 [2 4 1 3 7 8 5 6 9]
 [8 9 3 2 5 6 4 7 1]
 [6 5 7 4 9 1 8 3 2]]
count : 7

• 無事解くことができていました。
• 今回の問題に関しては再帰が7回で済んでいたが，ものによっては1万回以上のものもあった。

まとめ

• 今回は数独をPythonで解くためのプログラムを書いた。
• Pythonという言語上再帰は得意じゃないと思うのでもっと早い方法もあるはず
• プログラムのわかりやすさを優先したのでもっと良いアルゴリズムはあると思います。