世界で最も難しい数独を解決するにはどうすればよいですか？'

深さ優先探索で単一の値を推測する最適ではありません。

それで、これが幅優先仮説/反証法に基づく推論チェーンです（私の継子はしぶしぶ「知識に基づいた推測」と呼んでいます）。

矛盾を含むチェーンをたどるだけで、数独の23の変種を解くために、コンピューター支援ソルバーで使用するのが最適です。ただし、それに続くための特別なアルゴリズムは必要ありません（私は自分で作成した最適化されていないPythonプログラムを使用しているため、実際のコンピューティングはありません。

表記は、スプレッドシートの規則（列=文字、行=数字）（または、必要に応じてチェス）に従います。

STA Original Sudoku G8: 3,9 HYP # I8: 3,9 DIS # I8: 3,9 # B1: 1,2 => CTR => B1: 6 STA # I8: 3,9 + B1: 6 DIS # I8: 3,9 + B1: 6 # A2: 1,2 => CTR => A2: 5,9 STA # I8: 3,9 + B1: 6 + A2: 5,9 DIS # I8: 3,9 + B1: 6 + A2: 5,9 # B5: 1,2 => CTR => B5: 3,8 DIS # I8: 3,9 + B1: 6 + A2: 5,9 + B5: 3,8 => CTR => I8: 2,7 STA I8: 2,7 HYP I8: 2,7 # G7: 5 DIS I8: 2,7 # G7: 5 # G4: 6 => CTR => G4: 1,8 STA I8: 2,7 # G7: 5 + G4: 1,8 DIS I8: 2,7 # G7: 5 + G4: 1,8 # C5: 2,9 => CTR => C5: 6 STA I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 DIS I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 # H3: 4,5 => CTR => H3: 8 DIS I8: 2,7 # G7: 5 + G4: 1,8 + C5: 6 + H3: 8 => CTR => G7: 3,9 STA I8: 2,7 + G7: 3,9 HYP I8: 2,7 + G7: 3,9 # A8: 3,4,6 DIS I8: 2,7 + G7: 3,9 # A8: 3,4,6 # A9: 3 => CTR => A9: 6,7 STA I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 DIS I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 # D7: 2,7 => CTR => D7: 4,9 STA I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9 PRF I8: 2,7 + G7: 3,9 # A8: 3,4,6 + A9: 6,7 + D7: 4,9 => SOL 

世界で最も難しい数独に手順のスクリーンショットと方法の簡単な説明を掲載しました。私は「知識に基づいた推測」によって難しいパズルを解くことにしか興味がないので、この数独は実際には宣伝されているほど難しくはないことがわかりました（1レベルの仮説+1先読み= 2レベルの仮説）。実際、2レベル以上の仮説と1つの先読み（= 3レベルの仮説）を必要とする数独はまだ見つかりませんでした。

コメント

• ソルバーは17エントリの数独’に対してどの程度公平ですか？例えば。 theconversation.com/ …
• @SimonStreicher 17の手がかりの数独、あなたは引用しています難しいですが、私のアルゴリズムのコンテキストで最も難しい数独の中にはありません。一般的に、手がかりの数と数独の硬さの間には相関関係はありません。分析した数独に関するいくつかの統計を掲載しました。
• @SimonStreicher トップ95数独のリストを分析（つまり、 95ハードパズル）。レベルハードの数独が5つあり（2レベルの仮説が必要です）、それでも 101の最もハードな数独より2レベル下です。
• 情報をありがとう、私は’まだこのすべてを理解しようとしていますが、幸いなことにあなたのウェブサイトは非常に徹底しています。
• @SimonStreicherその核となるのは、検索スペースを単一の値をアクティブ化することから、バイナリ決定を生成するために使用される簡単に認識できるパターン（ペア）に削減することです。可能性。例えば。cell1は2つの可能な値v1とv2を許可し、cell2は同じ可能な値を許可しますが、さらに1つ以上の他の可能性v3、v4、v5を許可します。したがって、cell1とcell2はペア（両方ともv1とv2を含む）であるか、セル2はv3、v4、v5のいずれかのみになります。次に、この仮説がチェックされます。

このパズルの場合、解決策は1つだけですが、少しインテリジェントな推測とチェックを除いて、既知のパターンは機能しません。手がかりを減らすために先を見越さなければならないステップの数はここでの測定基準であり、このパズルは解決可能な状態に到達するために9つの連続した推測を必要とします。

SudokuWikiのソルバーは、Javascriptで実行するのに時間がかかりすぎ、数値を推測するようにプログラムされていないため、取得できません。

このソリューションでは、正方形の値を仮定し、パズルを減らして、さらに仮定が必要かどうかを確認する必要があります。必要な場合は、別の仮定を作成して続行します。これは、本質的に、可能な解決策の深さ優先探索です。 sudoku-solutions のソルバーは、このパズルの解決策を考え出しますが、手順を提供するように求められた場合、次のように宣言します。

このソルバーは、論理によってパズルを完全に解決できませんでした。これは、論理的な解決策がないことを意味するものではありません。

その後、解決に使用した手順の をすぐにリストできません。これは、ソルバーがブルートフォース分岐推測を使用して解を見つける必要がある場合にのみ発生します。

その結果、私自身が「このパズルを解く方法」の答えを合理的に提供する方法はありません。したがって、これらの特定のチェーンを見つけて、他の膨大な量のチェーンが機能しない理由を説明する必要があります。

しかし、それはあなたのやり方です。正方形が数字であり、次に別の、次に別の、そして、「まだ意味があり、パズルを解くことができるシーケンスに到達するまで、または矛盾が発生してバックアップして再試行する必要があるまで、チェックを続けます。恐れ入りますが、これがこの質問に対する最善の答えだと思います。

パズルの解決策を求めたので、私はそれを提供できます（スポイラーブロックの上にマウスを置く）：

コメント

• 古き良き再帰。
• 再帰の深さは最大2回で解決できました。”ネイキッドシングル”戦略は、合計61812回実行されました（より高いレベルでキャッシュが実行された後、実行カウントは数百万になります）。 “非表示のシングル”戦略32892回（およびキャッシュから提供された別の28920）、深さ1のみの検索が実行されました256何度もキャッシュからさらに15回提供されました（これらの実行のほとんどは実際には次の実行内で行われたと思いますが、各時点で1つの推測のみが行われました）、そして、2レベルの検索（’ dが2つの推測を行う）は1回だけ実行され、それを取得しました。
• （これも、実行されなかった唯一のパズルです’ 1レベルの推測だけでプログラムをクラックする）

シンガポールの数独ソルバーの首相をダウンロードして、このパズルをフィードします（本当に行き詰まっている場合のみ）。信じられないかもしれませんが、その首相はかなり強力なプログラムを作成しました。しばらくの間行き詰まっているように見えますが、最終的には次の解決策が出てきます。

862 || 751 || 349
943 || 628 || 157
571 || 493 || 286
============
159 || 387 || 624
386 || 245 || 791
724 || 169 || 835
============
217 || 934 || 568
438 || 576 || 912
695 || 812 || 473

このパズルを発明した人によると、論理で解くことができるようです。ソルバーがそれを行うのに24時間かかりました。

注：このパズルには、質問とは異なる位置に7行目の1があります。このパズルには複数の解決策があります。

コメント

• この元のパズルに複数の解決策があるとは思えません（それが暗示されている場合）。PMへの入力’のソルバーはおそらく間違っています。行3、列7は” 1 “、 ” 7 “（監視の1つ）ではありません。exeへの正しい入力が与えられると、既知のソリューションが出力されます。
• @SimonStreicher間違った入力は、行7、列3にあり、7は1である必要があります
• 5秒以上スタックしますか？私の非常に単純なソルバーは、なんとかそれを取得できます時間の長さ。

別のコンピューターベースのソリューションを追加してから、 MiniZincモデリング言語次のプログラムを作成できます：

int: n; array[1..n, 1..n] of 0..n: initial_grid; int: reg; array[1..n, 1..n] of 1..reg: regions; array[1..n, 1..n] of var 1..n: final_grid; include "alldifferent.mzn"; constraint forall(r, c in 1..n)(initial_grid[r, c] = 0 \/ initial_grid[r, c] = final_grid[r, c]); constraint forall(r in 1..n)(alldifferent([ final_grid[r, c] | c in 1..n ])); constraint forall(c in 1..n)(alldifferent([ final_grid[r, c] | r in 1..n ])); constraint forall(region in 1..reg)(alldifferent([ final_grid[r, c] | r, c in 1..n where regions[r, c] = region ])); solve satisfy; output [ show_int(1, final_grid[r, c]) ++ if c = n then ("\n" ++ if (r mod 3 = 0 /\ r < n) then "---------------------\n" else "" endif ) elseif c mod 3 = 0 then " | " else " " endif | r, c in 1..n ]; 

適切なデータとともにファイル：

n = 9; reg = 9; regions = array2d(1..9, 1..9, [ 3 * (row div 3) + col div 3 + 1 | row, col in 0..8 ]); initial_grid = [| 8, 0, 0, 0, 0, 0, 0, 0, 0, | 0, 0, 3, 6, 0, 0, 0, 0, 0, | 0, 7, 0, 0, 9, 0, 2, 0, 0, | 0, 5, 0, 0, 0, 7, 0, 0, 0, | 0, 0, 0, 0, 4, 5, 7, 0, 0, | 0, 0, 0, 1, 0, 0, 0, 3, 0, | 0, 0, 1, 0, 0, 0, 0, 6, 8, | 0, 0, 8, 5, 0, 0, 0, 1, 0, | 0, 9, 0, 0, 0, 0, 4, 0, 0 |] ; 

かなり標準的なラップトップでデフォルトのソルバーを使用すると、ソリューションは100ミリ秒で出力され、PMLeeのC ++実装を大幅に上回ります。マージン。

コメント

• このアルゴリズムは線形計画法に基づいていますか？
• ‘-ソルバーは制約プログラミングソルバーであり、問題は実際には線形ではないのでうまく機能しますが、一連の制約です。いくつかのかなり基本的な検索方法で可能な解決策のスペースを減らすためのヒューリスティックの組み合わせ。
• I ‘感動しました。私のマニュアルはとてもシンプルなので、 Kotlinのlverは、最大2の検索深度を使用して、ラップトップで約5秒でそれを打ち負かします。