数独パズルを解くコードを Python で書きたいと思っています。この目的に適したアルゴリズムについて何か考えがありますか。ボックス全体に可能なすべての数字を入力して解決し、対応するボックスに既知の値を挿入するアルゴリズムについてネットのどこかで読みました。既知の値の行と列から、既知の値が削除されます。これよりアルゴリズムを書くのを手伝ってください。また、ユーザーから既知の値を読み取る方法についても混乱しています。コンソールから値を 1 つずつ入力するのは非常に困難です。GUIを使用する以外にこれを行う簡単な方法はありますか?
質問する
144102 次
11 に答える
33
これが私のPythonでの数独ソルバーです。単純なバックトラッキング アルゴリズムを使用してパズルを解きます。簡単にするために、入力の検証や派手な出力は行われません。問題を解決するのは最低限のコードです。
アルゴリズム
- 指定されたセルのすべての正当な値を見つける
- 正当な値ごとに、再帰的に進み、グリッドを解こうとします
解決
部分的に数字で満たされた 9X9 グリッドが必要です。値が 0 のセルは、入力されていないことを示します。
コード
def findNextCellToFill(grid, i, j):
for x in range(i,9):
for y in range(j,9):
if grid[x][y] == 0:
return x,y
for x in range(0,9):
for y in range(0,9):
if grid[x][y] == 0:
return x,y
return -1,-1
def isValid(grid, i, j, e):
rowOk = all([e != grid[i][x] for x in range(9)])
if rowOk:
columnOk = all([e != grid[x][j] for x in range(9)])
if columnOk:
# finding the top left x,y co-ordinates of the section containing the i,j cell
secTopX, secTopY = 3 *(i//3), 3 *(j//3) #floored quotient should be used here.
for x in range(secTopX, secTopX+3):
for y in range(secTopY, secTopY+3):
if grid[x][y] == e:
return False
return True
return False
def solveSudoku(grid, i=0, j=0):
i,j = findNextCellToFill(grid, i, j)
if i == -1:
return True
for e in range(1,10):
if isValid(grid,i,j,e):
grid[i][j] = e
if solveSudoku(grid, i, j):
return True
# Undo the current cell for backtracking
grid[i][j] = 0
return False
コードのテスト
>>> input = [[5,1,7,6,0,0,0,3,4],[2,8,9,0,0,4,0,0,0],[3,4,6,2,0,5,0,9,0],[6,0,2,0,0,0,0,1,0],[0,3,8,0,0,6,0,4,7],[0,0,0,0,0,0,0,0,0],[0,9,0,0,0,0,0,7,8],[7,0,3,4,0,0,5,6,0],[0,0,0,0,0,0,0,0,0]]
>>> solveSudoku(input)
True
>>> input
[[5, 1, 7, 6, 9, 8, 2, 3, 4], [2, 8, 9, 1, 3, 4, 7, 5, 6], [3, 4, 6, 2, 7, 5, 8, 9, 1], [6, 7, 2, 8, 4, 9, 3, 1, 5], [1, 3, 8, 5, 2, 6, 9, 4, 7], [9, 5, 4, 7, 1, 3, 6, 8, 2], [4, 9, 5, 3, 6, 2, 1, 7, 8], [7, 2, 3, 4, 8, 1, 5, 6, 9], [8, 6, 1, 9, 5, 7, 4, 2, 3]]
上記のものは、多くの場所で説明されている非常に基本的なバックトラッキング アルゴリズムです。しかし、私が遭遇した数独解決戦略の中で最も興味深く自然なものは、ここからのものです
于 2013-11-29T06:20:28.143 に答える
9
これは、ハリの答えに基づくはるかに高速なソリューションです。基本的な違いは、値が割り当てられていないセルの可能な値のセットを保持することです。したがって、新しい値を試すときは、有効な値のみを試し、この選択が残りの数独に何を意味するかを伝えます。伝播ステップでは、各セルの有効な値のセットから、行、列、または同じブロックに既に表示されている値を削除します。セットに数値が 1 つしか残っていない場合、位置 (セル) にはその値が必要であることがわかります。
この方法は、フォワード チェックおよび先読みとして知られています ( http://ktiml.mff.cuni.cz/~bartak/constraints/propagation.html )。
以下の実装では 1 回の反復 (solve の呼び出し) が必要ですが、hari の実装では 487 回が必要です。もちろん、私のコードはもう少し長くなります。伝播方法も最適ではありません。
import sys
from copy import deepcopy
def output(a):
sys.stdout.write(str(a))
N = 9
field = [[5,1,7,6,0,0,0,3,4],
[2,8,9,0,0,4,0,0,0],
[3,4,6,2,0,5,0,9,0],
[6,0,2,0,0,0,0,1,0],
[0,3,8,0,0,6,0,4,7],
[0,0,0,0,0,0,0,0,0],
[0,9,0,0,0,0,0,7,8],
[7,0,3,4,0,0,5,6,0],
[0,0,0,0,0,0,0,0,0]]
def print_field(field):
if not field:
output("No solution")
return
for i in range(N):
for j in range(N):
cell = field[i][j]
if cell == 0 or isinstance(cell, set):
output('.')
else:
output(cell)
if (j + 1) % 3 == 0 and j < 8:
output(' |')
if j != 8:
output(' ')
output('\n')
if (i + 1) % 3 == 0 and i < 8:
output("- - - + - - - + - - -\n")
def read(field):
""" Read field into state (replace 0 with set of possible values) """
state = deepcopy(field)
for i in range(N):
for j in range(N):
cell = state[i][j]
if cell == 0:
state[i][j] = set(range(1,10))
return state
state = read(field)
def done(state):
""" Are we done? """
for row in state:
for cell in row:
if isinstance(cell, set):
return False
return True
def propagate_step(state):
"""
Propagate one step.
@return: A two-tuple that says whether the configuration
is solvable and whether the propagation changed
the state.
"""
new_units = False
# propagate row rule
for i in range(N):
row = state[i]
values = set([x for x in row if not isinstance(x, set)])
for j in range(N):
if isinstance(state[i][j], set):
state[i][j] -= values
if len(state[i][j]) == 1:
val = state[i][j].pop()
state[i][j] = val
values.add(val)
new_units = True
elif len(state[i][j]) == 0:
return False, None
# propagate column rule
for j in range(N):
column = [state[x][j] for x in range(N)]
values = set([x for x in column if not isinstance(x, set)])
for i in range(N):
if isinstance(state[i][j], set):
state[i][j] -= values
if len(state[i][j]) == 1:
val = state[i][j].pop()
state[i][j] = val
values.add(val)
new_units = True
elif len(state[i][j]) == 0:
return False, None
# propagate cell rule
for x in range(3):
for y in range(3):
values = set()
for i in range(3 * x, 3 * x + 3):
for j in range(3 * y, 3 * y + 3):
cell = state[i][j]
if not isinstance(cell, set):
values.add(cell)
for i in range(3 * x, 3 * x + 3):
for j in range(3 * y, 3 * y + 3):
if isinstance(state[i][j], set):
state[i][j] -= values
if len(state[i][j]) == 1:
val = state[i][j].pop()
state[i][j] = val
values.add(val)
new_units = True
elif len(state[i][j]) == 0:
return False, None
return True, new_units
def propagate(state):
""" Propagate until we reach a fixpoint """
while True:
solvable, new_unit = propagate_step(state)
if not solvable:
return False
if not new_unit:
return True
def solve(state):
""" Solve sudoku """
solvable = propagate(state)
if not solvable:
return None
if done(state):
return state
for i in range(N):
for j in range(N):
cell = state[i][j]
if isinstance(cell, set):
for value in cell:
new_state = deepcopy(state)
new_state[i][j] = value
solved = solve(new_state)
if solved is not None:
return solved
return None
print_field(solve(state))
于 2016-02-19T08:04:32.487 に答える
5
簡単なものを解決する簡単なプログラムを書きました。スペースと数字を含む単なるマトリックスであるファイルから入力を取得しました。それを解決するためのデータ構造は、ビット マスクの 9 x 9 マトリックスだけでした。ビットマスクは、特定の位置でまだ可能な数字を指定します。ファイルから数値を入力すると、既知の各場所の横にあるすべての行/列の数値が減少します。それが完了したら、マトリックスを繰り返し処理し、可能な数を減らします。各場所に 1 つのオプションしか残っていない場合は、完了です。しかし、さらに作業が必要な数独もあります。これらについては、ブルート フォースを使用できます。機能する組み合わせが見つかるまで、残りの可能な組み合わせをすべて試してください。
于 2009-11-08T18:16:35.547 に答える
1
完全なコードを書くつもりはありませんが、ずっと前に数独ソルバーを作成しました。常に解決するとは限らないことがわかりました (新聞を持っているときに人々が行うことは不完全です!) が、今ではその方法を知っていると思います。
- セットアップ: 各正方形に対して、許可された数字を示す各数字のフラグのセットを用意します。
- 取り消し線: 電車に乗っている人が紙の上で解くのと同じように、既知の数字に繰り返し取り消し線を引くことができます。数字が 1 つだけ残っているマスは、別のクロス アウトをトリガーします。これにより、パズル全体が解決されるか、トリガーが不足します。前回立ち寄ったところです。
- 順列: 9 つしかありません! = 362880 の方法で 9 つの数字を並べ替え、最新のシステムで簡単に事前計算できます。すべての行、列、および 3x3 の正方形は、これらの順列のいずれかでなければなりません。そこにたくさんの数字があれば、バツ印で行ったことを行うことができます。行/列/3x3 ごとに、9 の 1/9 を消すことができます。数字が 1 つの場合は順列、2 つある場合は 1/(8*9) などです。
- 相互順列: これで一連の潜在的な順列を含む一連の行と列ができました。しかし、別の制約があります。行を設定すると、列と 3x3 は大幅に削減されます。ここからツリー検索を実行して、解決策を見つけることができます。
于 2016-02-19T08:26:59.213 に答える
0
これは、Tensorflow と mnist と自動ソルバーを使用して、少し前に行ったプロジェクトです。ただし、ソルバーアルゴリズムは十分に文書化されていません:)
于 2021-04-24T12:39:31.817 に答える