今日からPythonで数独ソルバーを作ってみよう! 数独パズルは、毎日の新聞に掲載され、多くの人々の関心を集めている非常に人気のあるパズルです。
数独パズルとその一般化については、多くの難問、未解決問題があり、特に多くの数学愛好家にとってこのパズルは興味深いものとなっています。
数独パズルとは？
数独は、1～9の整数で空欄を埋めるパズルです。
1から9までの整数が、各行、各列に一度ずつ現れるように、空欄を埋める必要があります。
1から9までのすべての数字が，すべての行，すべての列，太字で表示された3×3のマスに一度ずつ現れるように
そして、太い枠で囲まれた3×3の小さな箱の中に1つずつ
1から9までのすべての数字が、すべての行、すべての列、太い枠で囲まれた3×3の箱の中に入るようにします。
このパズルは、難易度が異なる場合があります。
数独の難易度が上がれば上がるほど、計算科学者にとってより挑戦的な研究課題となります。
計算科学者にとっての難問となります。
難易度の高いパズルは、ほとんどの場合、規定された記号が少なく
記号が少ないです。
エンターテイメントとして公開されている数独は
ユニークな解答があります。
数独はユニークな解答を持つ場合、整形式と呼ばれます。
もう一つの研究課題は、どの程度の数のマスを埋めれば整形されたことになるかを決めることです。
17個の記号で構成される数独は存在します。
しかし、16個のヒントしかない数独が存在するかどうかは不明です。
Pythonで数独パズルを解くためのステップ
- この数独の解法では、まず2次元行列の大きさを変数Mに代入する(M*M)。
- 次に、グリッドを表示するためのユーティリティ関数(puzzle)を代入します。
- その後、行と列に num を代入します。
- もし、同じ行、同じ列、特定の3*3行列に同じ番号があれば、’false’が返されます。
- 次に、8行目、9列目に到達したかどうかを確認し、それ以上の後退を停止するためにtrueを返します。
- 次に、列の値が9になったら、次の行と列に移動します。
- さらに、現在のグリッドの位置が0より大きいかどうかを確認し、次の列まで反復します。
- 安全な場所かどうか確認した後、次の列に移動し、グリッドの現在の位置（行、列）にnumを割り当てます。その後、次の列で次の可能性をチェックします。
- 仮定が誤っていたため、割り当てられたnumを破棄し、別のnum値で次の仮定を行う。
Pythonで数独ソルバーを実装する
Pythonで数独ソルバーを作成するためにバックトラック法を使います。
バックトラックとは、現在の解が完全な解にならないと判断したら、すぐに前のステップに戻ることです。
このバックトラックの原理を利用して、数独のアルゴリズムを実装します。
M = 9
def puzzle(a):
for i in range(M):
for j in range(M):
print(a[i][j],end = " ")
print()
def solve(grid, row, col, num):
for x in range(9):
if grid[row][x] == num:
return False
for x in range(9):
if grid[x][col] == num:
return False
startRow = row - row % 3
startCol = col - col % 3
for i in range(3):
for j in range(3):
if grid[i + startRow][j + startCol] == num:
return False
return True
def Suduko(grid, row, col):
if (row == M - 1 and col == M):
return True
if col == M:
row += 1
col = 0
if grid[row][col] > 0:
return Suduko(grid, row, col + 1)
for num in range(1, M + 1, 1):
if solve(grid, row, col, num):
grid[row][col] = num
if Suduko(grid, row, col + 1):
return True
grid[row][col] = 0
return False
'''0 means the cells where no value is assigned'''grid = [[2, 5, 0, 0, 3, 0, 9, 0, 1],
[0, 1, 0, 0, 0, 4, 0, 0, 0],
[4, 0, 7, 0, 0, 0, 2, 0, 8],
[0, 0, 5, 2, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 9, 8, 1, 0, 0],
[0, 4, 0, 0, 0, 3, 0, 0, 0],
[0, 0, 0, 3, 6, 0, 0, 7, 2],
[0, 7, 0, 0, 0, 0, 0, 0, 3],
[9, 0, 3, 0, 0, 0, 6, 0, 4]]
if (Suduko(grid, 0, 0)):
puzzle(grid)
else:
print("Solution does not exist:(")
|
結果を出力すると、以下の様になります。
====================== RESTART: C:/Users/SIDDHI/sudoku.py ===========
2 5 8 7 3 6 9 4 1
6 1 9 8 2 4 3 5 7
4 3 7 9 1 5 2 6 8
3 9 5 2 7 1 4 8 6
7 6 2 4 9 8 1 3 5
8 4 1 6 5 3 7 2 9
1 8 4 3 6 9 5 7 2
5 7 6 1 4 2 8 9 3
9 2 3 5 8 7 6 1 4
|
まとめ
Pythonで数独ソルバーを作るのはここまでです。
この記事を読んで、私たちがどのようにコードを実装したかを知っていただけたなら幸いです。
Psst… Pythonで数独ソルバーを作る簡単な方法もあります!
https://pypi.org/project/py-sudoku/ から sudoku py-sudoku.PyPI モジュールをインポートすることができます。
これは、m×nの数独パズルを生成して解くシンプルなPythonプログラムです。
かなりクールでしょう? さあ、数独で遊んでみましょう!