Pythonで数独を解く

Pythonで数独ソルバーを作ってみました。

この記事は書きかけです

数独とは

マスの枠に以下の3つのルールを守って までの数字を当てはめていくゲームです。ナンプレとかナンバープレースみたいな名前で呼ばれていたりもします。

ルール

  1. 同じ行に同じ数字が入ってはいけない
  2. 同じ列に同じ数字が入ってはいけない
  3. 同じブロックに同じ数字が入ってはいけない

アルゴリズム

比較的単純な深さ優先探索(Depth First Search)というアルゴリズムを用いました。

実際のコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
def solve(arr, cell):
"""単純なdfsで解く"""

# 求まったとき
if cell == 81:
print(*arr, sep="\n")
exit()

i, j = cell//9, cell%9
if arr[i][j] == 0:

# 順に代入する
for n in range(1, 10):

# --- 行 ---
if n in arr[i]:
continue

# --- 列 ---
is_in_col = False
for r in range(9):
is_in_col |= arr[r][j] == n
if is_in_col:
continue

# --- ブロック ---
is_in_block = False
for r in range(i//3*3, i//3*3+3):
for c in range(j//3*3, j//3*3+3):
is_in_block |= arr[r][c] == n
if is_in_block:
continue

# 条件をみたしていたとき
arr[i][j] = n
solve(arr, cell+1)
arr[i][j] = 0
else:
solve(arr, cell+1)



def main():
arr = []

solve(arr, 0)


if __name__ == "__main__":
main()

おまけ

AtCoderの問題に似たようなものがありました。

この問題が水diffだったので、数独を解くアルゴリズムも水diffくらいかなと思います。


このページはHexoStellarを使用して作成されました。