今回は数独をプログラムで解いてみます。

解説動画はこちら



さて数独のルールですが
9x9のマスがあり初期配置で数値が置かれている。

空いているマスに1〜9のいずれかの数字を入れる。

縦・横の各列及び
太線で囲まれた3×3のブロック内に
同じ数字が複数入ってはいけない。
download

コレをプログラムで解いていきましょう。

考え方としては

事前:用意された数値埋めて
空白マスを0として埋めたリスト型を用意する

(1) 左上から右下へと順に0を調べていく
(2) 0があれば、その時点で配置可能な数字を調べる
(3) 配置可能な数字を仮に配置して、次のマスを調べていく
(4) もし配置がうまくいかなければ(3)に戻る
(5) 最後のマスに到達するまで、(2)以降の処理を繰り返す
(6) 最後に到達したら結果を出力する

こんな感じです。

プログラムの実装を考えてみましょう。

考えたく無い方はこちらが
実装例になります。
# 行、列、ブロックのチェック
def is_valid(grid, y, x, val):
    if val in grid[y]:
        return False 
    if val in [i[x] for i in grid]:
        return False
    # NxNブロックの判定
    t_x, t_y = (x//N) * N, (y//N) * N
    block = [i[t_x:t_x + N] for i in grid[t_y:t_y + N]]
    if val in sum(block, []):
        return False
    return True

# 0の座標を返す
def find_next(grid):
    for y in range(N*N):
        for x in range(N*N):
            if grid[y][x] == 0:
                return x , y
    return -1, -1

# 数独を解く
def solve(grid, y=0, x=0):
    x , y = find_next(grid)
    if -1==x or -1==y:
        return True
    for val in range(1, N*N+1):
        if is_valid(grid, y, x, val):
            grid[y][x] = val
            if solve(grid, y, x):
                return True
            grid[y][x] = 0
    return False

# ブロックの大きさ
N=3
# 初期配列
input_num = [
[5, 8, 7, 2, 0, 0, 0, 0, 1],
[9, 0, 0, 0, 0, 0, 4, 0, 0],
[0, 0, 0, 1, 8, 0, 6, 0, 0],
[0, 0, 0, 0, 0, 4, 7, 2, 0],
[0, 5, 0, 8, 7, 0, 0, 4, 0],
[0, 0, 2, 0, 0, 0, 0, 0, 0],
[0, 4, 0, 0, 0, 3, 0, 0, 0],
[0, 0, 0, 0, 0, 7, 2, 9, 3],
[0, 2, 1, 0, 0, 0, 0, 0, 0]]

solve(input_num)
for row in input_num:
    print(' , '.join([str(i) for i  in row]))
5 , 8 , 7 , 2 , 4 , 6 , 9 , 3 , 1
9 , 1 , 6 , 7 , 3 , 5 , 4 , 8 , 2
2 , 3 , 4 , 1 , 8 , 9 , 6 , 5 , 7
1 , 9 , 8 , 3 , 6 , 4 , 7 , 2 , 5
6 , 5 , 3 , 8 , 7 , 2 , 1 , 4 , 9
4 , 7 , 2 , 9 , 5 , 1 , 3 , 6 , 8
7 , 4 , 9 , 5 , 2 , 3 , 8 , 1 , 6
8 , 6 , 5 , 4 , 1 , 7 , 2 , 9 , 3
3 , 2 , 1 , 6 , 9 , 8 , 5 , 7 , 4

一応この実装では
9x9以上の数独にも対応してますが
16x16以上は時間がかかるので
試してませんwww

数独は色々な実装を考えることができ
解き方は1つでは無いかと思います。

もっと効率の良い
実装をすれば16x16の数独なども
素早く解けるのでは無いかと思います。

こういったパズルゲームを
解くのは面白いですよね

今日はコレまでです
それでは。