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

解説動画はこちら



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

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

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

考え方としては



こんな感じです。

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

考えたく無い方はこちらが
実装例になります。

# 行、列、ブロックのチェック
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]))

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

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

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

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

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

タグ ：

Python

プログラミング

数独

パズル