数独を解くアルゴリズム

標準的な数独は、9×9のグリッドに81個のセルと9個のボックスがあり、各ボックスは最初、中央、または最後の3行と最初、中央、または最後の3列が交差する位置にあります。各セルには1から9までの数字を入れることができますが、各数字は各行、列、ボックスに1回しか出現できません。数独はいくつかのセルに数字（ヒント）が入った状態から始まり、残りのセルを解くことが目的です。正しい数独には1つの解があります。^[1]プレイヤーや研究者は、さまざまなコンピューターアルゴリズムを使用して数独を解き、その特性を研究し、興味深い対称性やその他の特性を持つ数独などの新しいパズルを作成します。

9×9 パズル ( n = 9) をほんの一瞬で解くコンピュータ アルゴリズムはいくつかありますが、 nが増加すると組み合わせ爆発が発生し、 n が増加するにつれて構築、分析、および解くことができる数独の特性に制限が生じます。

愛好家の中には、バックトラッキングアルゴリズムを使用して数独パズルを解くコンピュータプログラムを開発している人もいます。これは、ブルートフォース探索の一種です。^[3]バックトラッキングは、幅優先探索とは対照的に深さ優先探索^{であり、1つのブランチを完全に探索してから別のブランチに移動します。約5.96 x 10 26の}最終的なグリッドが存在することが確立されていますが、ブルートフォースアルゴリズムは数独パズルを解くための実用的な方法になり得ます。

ブルートフォースアルゴリズムは、ある順序で空のセルにアクセスし、数字を順番に埋めるか、数字が有効でないと判明した場合はバックトラックします。^{[4] [5] [6] [7]}簡単に言えば、プログラムは最初のセルに数字「1」を配置し、そこに数字を配置できるかどうかをチェックすることでパズルを解きます。違反がない場合（行、列、ボックスの制約をチェック）、アルゴリズムは次のセルに進み、そのセルに「1」を配置します。違反をチェックしているときに、「1」が許可されていないことが判明した場合、値は「2」に進みます。9つの数字のいずれも許可されていないセルが見つかった場合、アルゴリズムはそのセルを空白のままにして、前のセルに戻ります。そのセルの値は1ずつ増加します。これは、最後の（81番目の）セルで許可されている値が見つかるまで繰り返されます。

アニメーションは、この方法で数独を解く方法を示しています。アルゴリズムが未解決の各セルを可能な解法でテストしている間、パズルのヒント (赤い数字) は固定されたままです。既存のセットが数独の制約を満たしていないことが判明した場合、アルゴリズムは以前にテストされたすべての値を破棄する可能性があることに注意してください。

この方法の利点は次のとおりです。

• 解決は保証されます（パズルが有効である限り）。
• 解く時間は難易度とほとんど関係ありません。^{[疑わしい–議論する]}
• このアルゴリズム (およびプログラム コード) は、特に最も難しいパズルの解決を保証する強力なアルゴリズムと比較すると、他のアルゴリズムよりも単純です。

この方法の欠点は、演繹法をモデルにしたアルゴリズムに比べて解くのに時間がかかることである。あるプログラマーは、このようなアルゴリズムでは通常、数独を解くのに 15,000 サイクル、最大で 900,000 サイクル必要であり、各サイクルは数独のセルを移動する「ポインタ」の位置の変化である、と報告した。^{[8] [9]}

バックトラッキングを使用する別のアプローチは、標準的な数独の解法では、すべての個別のシンボル (値) の分布が 46656 パターンのいずれかにならなければならないという事実に基づいています。手動の数独の解法では、この手法はパターン オーバーレイまたはテンプレートの使用と呼ばれ、最後の値のみの入力に限定されます。プログラムの開始時に、すべての可能なパターンを含むライブラリを読み込むか作成することができます。次に、指定されたすべてのシンボルに、指定されたヒントに従ったパターンを含むフィルター セットが割り当てられます。最後のステップ、実際のバックトラッキング部分では、これらのセットのパターンを競合しない方法で組み合わせるかオーバーレイして、許容される組み合わせが 1 つ見つかるまで試行します。ビット ベクトルを使用すると、すべてのテストで行と列にわたるネストされた反復処理ではなく、ビット単位の論理演算のみが必要になるため、実装は非常に簡単です。フィルタリング中にパターンのセットをさらに減らすことで、大幅な最適化を実現できます。疑わしいパターンをすべて、他のシンボルに対してすでに受け入れられているすべての縮小セットに対してテストすることで、バックトラックに残されるパターンの総数は大幅に減少します。

また、すべての数独ブルートフォース技法と同様に、いくつかの「簡単な」値を埋める最も単純な解決方法を最初に適用することで、実行時間を大幅に短縮できます。

数独はバックトラックに対抗するように構築することができます。ソルバーが上から下に向かって（アニメーションのように）動くと仮定すると、ヒントが少ない（17）、一番上の行にヒントがなく、最初の行の解答が「987654321」であるパズルは、アルゴリズムに反する動作をします。したがって、プログラムは、パズルを満たすグリッドに到達する前に、上に向かって「数える」のにかなりの時間を費やすことになります。あるケースでは、プログラマーは、ブルートフォース プログラムがそのような数独の解答に到達するのに 6 時間かかることを発見しました（2008 年頃のコンピューターを使用していましたが）。そのような数独は、今日では徹底的な検索ルーチンとより高速なプロセッサーを使用して 1 秒未満で解くことができます。^{[10] p:25}

数独は確率的（ランダムベース）アルゴリズムを使用して解くことができます。^{[11] [12]}この方法の例は次のとおりです。

1. グリッド内の空白のセルにランダムに番号を割り当てます。
2. エラーの数を計算します。
3. 間違いの数がゼロになるまで、挿入した数字を「シャッフル」します。

次に、パズルの解が見つかります。数字をシャッフルするアプローチには、シミュレーテッドアニーリング、遺伝的アルゴリズム、タブーサーチなどがあります。確率ベースのアルゴリズムは高速であることが知られていますが、演繹的手法ほど高速ではないかもしれません。ただし、後者とは異なり、最適化アルゴリズムでは問題が論理的に解決可能である必要はなく、より広範囲の問題を解決できる可能性があります。グラフの色付け用に設計されたアルゴリズムも、数独で優れたパフォーマンスを発揮することが知られています。^[13]数独を整数線形計画問題として表現することもできます。このようなアプローチはすぐに解に近づき、最後に向かって分岐を使用できます。単体アルゴリズムは適切な数独を解くことができ、数独が有効でない（解がない）かどうかを示します。複数の解がある場合（適切でない数独）、単体アルゴリズムは通常、いくつかのマス目に1桁を超える小数点付きの解を生成します。ただし、適切な数独の場合、線形計画法の事前解決手法だけで、単体反復を必要とせずに解を導き出すことができます。 LP 問題の簡約化のために事前解決手法で使用される論理ルールには、人間が数独を解くために使用する論理ルールのセットが含まれます。

数独は制約充足問題としてモデル化することもできます。ヘルムート・シモニスは論文「制約問題としての数独」^[14]で、制約に基づいた多くの推論アルゴリズムについて説明しており、これらのアルゴリズムは問題のモデル化と解決に適用できます。制約ソルバーの中には数独をモデル化して解く方法が含まれているものもあり、簡単な数独を解くのに100行未満のコードで済むプログラムもあります。^{[15] [16]}コードが強力な推論アルゴリズムを採用している場合、バックトラッキングを組み込む必要があるのは最も難しい数独だけです。制約モデルベースのアルゴリズムとバックトラッキングを組み合わせたアルゴリズムには、数ミリ秒のオーダーで^[17]高速に解けるという利点があり、すべての数独を解くことができます。^[5]

数独パズルは、正確なカバー問題、より正確には正確なヒットセット問題として説明できます。これにより、問題を簡潔に説明し、効率的に解くことができます。数独を正確なカバー問題としてモデル化し、Knuth の Algorithm XやDancing Linksテクニックなどのアルゴリズムを使用することは、「数独パズルのすべての可能な解を [マイクロ秒単位で測定] 迅速に見つけるための最適な方法です。」^[18] 別の方法として、ガウス消去法と列と行のヒットを組み合わせて使用​​する方法があります。

Q を9x9 数独行列、N = {1, 2, 3, 4, 5, 6, 7, 8, 9}とし、 X は一般的な行、列、またはブロックを表します。N は、Q を埋めるための記号と、任意のXの 9 つの要素のインデックス セットを提供します。 Qの指定された要素q は、 QからNへの一価関係を表します。解R は全関係であるため、関数です。数独のルールでは、 RからXへの制限は一対一であることが求められるため、 Xに制限された部分解C は、Nの部分順列になります。

T = { X  : X はQの行、列、またはブロック}とすると、 Tには27 個の要素があります。配置は、部分的な順列またはN上の順列のいずれかです。Z をN上のすべての配置の集合とします。部分的なソリューションC は、互換性のある配置を必要とする関係A (1 対 3) とBの組み合わせとして規則を含むように再定式化できます。

${\displaystyle Q\xrightarrow {A} T\xrightarrow {B} Z\quad {\text{with}}\quad A;B\subseteq C.}$

パズルの解決、Qに入るための新しいqの提案は禁止された配置から来ており、Q x ZのCの補数：関係の計算で役立つツールは残差です： ${\displaystyle {\bar {C}},}$

${\displaystyle A\backslash C={\overline {A^{T};{\bar {C}}}}}$T をZにマッピングし、

${\displaystyle C/B={\overline {{\bar {C}};B^{T}}}}$QをTにマッピングします。

• 数独
• 数独の数学
• 組み合わせ爆発（ラテン方陣と比較した数独のグリッドカウントの要約付き）
• 数独用語集

• http://diuf.unifr.ch/pai/people/juillera/Sudoku/Sudoku.html Nicolas Juillerat による Sudoku Explainer (一般的な Sudoku の評価で人気) 2013-11-12 にWayback Machine でアーカイブ
• 数独パズルを解くための紙と鉛筆を使ったアルゴリズム