数独ソルバー Python
Sudoku は、論理と推理が好きな人に最も人気のある、論理ベースの数字配置パズル ゲームです。 数独パズルを解くことは、脳が集中力と論理的思考を向上させるのに役立ちます。
この記事では、Python を使用して数独を解く方法について説明します。
Python でバックトラッキング アルゴリズムを使用して数独を解く
計算上の問題の解決策を見つけるとき、バックトラッキング アルゴリズムは私たちが頻繁に使用する手法です。 数独を解いている間、塗りつぶされたボックスの数字が有効かどうかをチェックします。
有効でない場合は、1 から 9 までの他の数字をチェックします。有効な数字が見つからない場合は、前のオプションに戻ります。
行き止まりに達して前の選択に戻ると、選択を変更し、別の可能な解決策が得られます。
数独ソルバーとバックトラッキング アルゴリズムを実装する方法を考えてみましょう。
まず、パズルを形成してボードをセットアップする必要があります。
def setBoardFunc(puz):
global grid
print("\n---------------Sudoku Solver---------------\n")
print("Here is the Sudoku Problem :")
for i in range(0, len(puz), 9):
row = puz[i : i + 9]
temp = []
for block in row:
temp.append(int(block))
grid.append(temp)
printGridFunc()
ここでは、パズルを形成するために setBoardFunc() という名前の関数を定義しました。 ループ中に 9x9 パズルを設定し、空のセルを 0 で初期化します。
関数の操作が完了すると、puz で指定された入力が出力されます。 次に、グリッドを印刷する必要があります。 このステップは、指定された入力で 9x9 グリッドを出力します。
def printGridFunc():
global grid
for row in grid:
print(row)
次に、現在の値が現在のボックス内に配置できるかどうかを確認します。
def checkValidFunc(row, column, num):
global grid
for i in range(0, 9):
if grid[row][i] == num:
return False
for i in range(0, 9):
if grid[i][column] == num:
return False
square_row = (row // 3) * 3
square_col = (column // 3) * 3
for i in range(0, 3):
for j in range(0, 3):
if grid[square_row + i][square_col + j] == num:
return False
return True
このステップでは、指定された番号が特定のボックスに対して有効かどうかを確認します。 番号は、現在の場所に配置する同じ行、列、またはブロック ボックスのいずれのボックスであってもなりません。
数値がその要件を満たし、true を返す場合、次の値に移動できます。 そうでない場合、その番号は拒否されます。 次に、バックトラッキング アルゴリズムに適応するすべてのブロックをトラバースする必要があります。
def solveFunc():
global grid
for row in range(9):
for column in range(9):
if grid[row][column] == 0:
for num in range(1, 10):
if checkValidFunc(row, column, num):
grid[row][column] = num
solveFunc()
grid[row][column] = 0
return
print("\nSolution for the Sudoku Problem: ")
printGridFunc()
このコード チャンクの後半部分では、数値が有効かどうかをチェックします。 ここでは、関数バックトラッキング アルゴリズムを導入しています。
まず、空のセルを検索します。 見つかった場合、解決された数独がそこにあり、指定された数独の解決策が出力されます。 空のボックスが見つかった場合は、反復によって 1 から 9 までの数字を推測します。
有効な数値が存在する場合は、solveFunc() を呼び出して次の空のセルに移動しますが、有効な推測がない場合は、関数の前の呼び出しでセルの値を 0 にリセットして続行します。 次の有効な数値を見つけるために繰り返します。
アルゴリズムが空のボックスを有効な数値で埋め尽くすと、プロセスをバックトラックしてプロセス全体を繰り返します。 最後に、グリッドを渡して関数を呼び出して、与えられた数独を解きましょう。
puz = (
"004300209005009001070060043006002087190007400050083000600000105003508690042910300"
)
grid = []
setBoardFunc(puz)
solveFunc()
完全なソース コード:
def setBoardFunc(puz):
global grid
print("\n---------------Sudoku Solver---------------\n")
print("Here is the Sudoku Problem :")
for i in range(0, len(puz), 9):
row = puz[i : i + 9]
temp = []
for block in row:
temp.append(int(block))
grid.append(temp)
printGridFunc()
def printGridFunc():
global grid
for row in grid:
print(row)
def checkValidFunc(row, column, num):
global grid
for i in range(0, 9):
if grid[row][i] == num:
return False
for i in range(0, 9):
if grid[i][column] == num:
return False
square_row = (row // 3) * 3
square_col = (column // 3) * 3
for i in range(0, 3):
for j in range(0, 3):
if grid[square_row + i][square_col + j] == num:
return False
return True
def solveFunc():
global grid
for row in range(9):
for column in range(9):
if grid[row][column] == 0:
for num in range(1, 10):
if checkValidFunc(row, column, num):
grid[row][column] = num
solveFunc()
grid[row][column] = 0
return
print("\nSolution for the Sudoku Problem: ")
printGridFunc()
puz = (
"004300209005009001070060043006002087190007400050083000600000105003508690042910300"
)
grid = []
setBoardFunc(puz)
solveFunc()
出力：
まとめ
解決する方法は他にもありますが、バックトラッキング アルゴリズムを使用すると数独の最終的な出力がより正確になりますが、多くの反復で構成されるため、より多くの時間がかかります。 ただし、数独パズルを解くことは、人の論理的思考を向上させ、余暇を過ごすエキサイティングな方法です。
Nimesha is a Full-stack Software Engineer for more than five years, he loves technology, as technology has the power to solve our many problems within just a minute. He have been contributing to various projects over the last 5+ years and working with almost all the so-called 03 tiers(DB, M-Tier, and Client). Recently, he has started working with DevOps technologies such as Azure administration, Kubernetes, Terraform automation, and Bash scripting as well.