5

未解決の数独を考えると、それがユニークな解決策を持っていることをどのように示すことができますか？

4

6 に答える 6

3

2つの解決策を見つけてください。

最も単純なアルゴリズムは、バックトラッキングを使用したブルートフォース再帰アルゴリズムです。最初の解決策を見つけたら、戻って2番目の解決策を探します。これは遅いですが、（ロジックのみに依存するアルゴリズムとは異なり）最終的にすべてのソリューションを見つけることができることが保証されています。したがって、このアルゴリズムが1つのソリューションのみを検出して終了した場合、そのソリューションは一意である必要があります。

これは簡単な問題では機能しますが、難しい問題では数時間または数日かかる場合があります。より高速にする必要がある場合に使用できる最適化は多数あります。

簡単な最適化は、各正方形の候補リストを追跡することです。各ステップで、候補が最も少ない正方形を見つけます。候補が1つしかない場合は、その番号を選択し、グリッドと他の正方形の候補を更新してから続行します。候補者がゼロの場合は、以前に行った推測が間違っていたことがわかっているので、後戻りする必要があります。

より高度な最適化には、推測せずに数値を推測できるパターンを探すことが含まれます。ここではいくつかの例を示します。

于 2011-02-19T19:02:50.770 に答える
3

次のような、最終的には一意ではないソリューションになる特定の構成があります。

* *  *  | * * * | * * *
* *  *  | * * * | * * *
* 12 12 | * * * | * * *
--------+-------+------
* *  *  | * * * | * * *
* *  *  | * * * | * * *
* 12 12 | * * * | * * *
--------+-------+------
* *  *  | * * * | * * *
* *  *  | * * * | * * *
* *  *  | * * * | * * *

ここで、*は任意の数にすることができ12、それらのセルでの唯一の可能性です。この場合、少なくとも2つの可能な解決策が確実にあります。

* * * | * * * | * * *    * * * | * * * | * * *
* * * | * * * | * * *    * * * | * * * | * * *
* 1 2 | * * * | * * *    * 2 1 | * * * | * * *
------+-------+------    ------+-------+------
* * * | * * * | * * *    * * * | * * * | * * *
* * * | * * * | * * *    * * * | * * * | * * *
* 2 1 | * * * | * * *    * 1 2 | * * * | * * *
------+-------+------    ------+-------+------
* * * | * * * | * * *    * * * | * * * | * * *
* * * | * * * | * * *    * * * | * * * | * * *
* * * | * * * | * * *    * * * | * * * | * * *

ボードの残りの部分を計算しなくても、この数独のソリューションはユニークではないと判断できます。ただし、場合によっては、パズルの解が一意ではないことを証明できる場合でも、パズルの解が一意であることを証明する唯一の方法は、ブルートフォースを使用して、可能な解のセットに含まれる解が1つだけであることを計算することです。

純粋なブルートフォースよりもいくつかのショートカットがありますが、ハイブリッドソルバーを作成するときは特に注意する必要があります。ほとんどの数独解法では、複数の解が存在する場合はそれを見つけることができますが、高度な数独解法の中には、適切な数独には独自の解があるという事実に依存しているため、2番目の解を見つけることができない場合があります。

于 2011-02-19T19:31:57.213 に答える
2

数独は、ボックスごとに1つずつ、81個の変数に対するCSPです。一番上の行（左から右）にA1からA9まで、一番下の行にI1-I9までの変数名を使用します。空白のボックスにはドメイン{1,2,3,4,5,6,7,8,9}があり、単一の値で構成されるドメインが既に入力されています。また、「すべて異なる」27の異なる制約があり、各行、列、およびボックス9のボックスに1つずつあります。

単純なパターンにはAC-3アルゴリズムを使用でき、より難しいパターンにはPC-2を使用できますが、これには計算コストが高くなります。

于 2013-10-31T09:17:00.267 に答える
0

私の意見では、唯一の方法はそれを解決することです。あなたがそれを解決することができるなら（推測せずに-100％の「動き」だけで）、それはそれがちょうど1つの解決策を持っていることを意味します。それを解決できない場合、私が見る唯一の方法は、ブルートフォースアルゴリズムを使用して、実際にいくつの解決策を見つけることができるかを確認することです。

于 2011-02-19T19:05:48.013 に答える
0

上記のように、バックトラッキングを伴うブルートフォース再帰アルゴリズムを使用できます。アルゴリズムを1回上向きに2回適用するだけで提案したいと思います。つまり、候補値は検索中に段階的に増加し、アルゴリズムを下向きに使用します。つまり、候補値は可能な最大数から1まで降順で調べられ、少なくとも2つの解を検出できます。昇順と降順のアプローチの結果が同じままである場合、パズルには独自の解決策があると言えます。

于 2019-06-10T18:23:35.757 に答える
0

バックトラッキング手法を使用して、考えられるすべてのソリューションを使い果たします。あなたが解決策を得るならば。ソリューションカウンター+1。カウンターが1を超えて増加した場合、このパズルに複数の解決策があると宣言して、プログラムを終了できます。それ以外の場合は、終了するまで待つ必要があります。カウンター=1の場合、1つの解決策があることを確認します。counter = 0の場合、解決策はありません。

于 2021-03-12T10:55:32.063 に答える