アルゴリズムXまたは木製パズルとダンスリンクの共通点は何ですか？

まえがき

パーティーに行ったら、25個の同じ数字からキューブを組み立てる必要があるパズルに出会いました。 私は彼女と一晩中過ごしましたが、ご想像のとおり、無駄でした。 しかし、私はそのようにあきらめることができませんでした。



自分ではできません-コンピューターを作りましょう。 すぐに言ってやった。 その結果、気まぐれなアルゴリズムに書かれたものは、4つのユニークなソリューションすべてを見つけるために一晩中働かなければなりませんでした。 比較のためにソリューションをグーグル検索する過程で、私はラップツールで3分でこのタスクに対処したBurr Toolsプログラムを見つけました。



この速度の違いにより、この問題を解決する方法と、そのような他のクラス全体を理解することができました。



















このパズルは、正確なカバレッジ問題の典型的な代表です 。



問題ステートメントは、次の例を使用して表示できます。 収集可能なカードを求めて店に来ます。 重複するカードのない完全なコレクションをまとめるには、どのデッキを購入する必要がありますか？



このようなタスクには、ドナルドクヌースのアルゴリズムXがあります。 しかし、アルゴリズムの検討に移る前に、キューブパズルを正確なカバレッジ問題に還元する方法を見てみましょう。

タスクの形式化

簡単にするために、4つの平らな角から大きな角を折り返すという同様の問題を解決します。 図が折り畳まれている場合、図の各正方形は1つのコーナーにのみ属します。これは、すでに、完全なカバレッジの問題の記述と非常によく似ています。











大きな数字のすべての正方形を数字で示し、その中の小さな角のすべての可能な位置を文字で示しましょう（ここでは、明確にするために、ソリューションに存在できない角の「悪い」位置を意図的に捨てています）。 12個の正方形のセットは、ALの規定でカバーしようとするものです。 タスクは、表形式（ 発生率マトリックス ）で表示することもできます。 列は正方形に対応し、行は角の位置に対応し、角の対応する位置が対応する正方形で覆われている場合、列と行の交点にあるユニットが配置されます。















少し目立たない方法で、すべてのピースが異なるパズル、または数独のようなゲームは、完全なカバレッジの問題に還元されます。 読者は、これらの状況を形式化する方法を独自に考えてください（もしそうなら、 答えはWikipediaにあります ）。

アルゴリズムX

アルゴリズムXは、タスクを元に戻しますが、列/行が少ないいくつかのステップで構成されます。 さらに、アルゴリズムは特定のステップで分岐することに注意してください。 言い換えれば、これはまだ多すぎるが、賢い:-)

手順1.行列Sの列cを選択します

幾何学的言語で列を選択するということは、まだカバーされていない正方形を選択することを意味します。 私たちの場合、それは正方形の24になります。

ステップ2. S _r、c = 1になるように、各行rのアルゴリズムを分岐します

ボックス24は、位置Aまたは位置Dのいずれかによって閉じられます。どちらかを選択するための前提条件はないため、両方のオプションを個別に検討します。 これは、オプションを列挙するステップです。 多くの場合、手順1で数を減らすために、任意の列ではなく、最小数のユニットを含む列を選択します。

ステップ3.選択された行rについて、 S _r、j = 1となるすべての列jを考慮します

行Aを選択し、ソリューションスタックに挿入します。 ここで、位置Aにあるすべての正方形を選択する必要があります。

ステップ4.列jのすべての非ゼロ要素について、それらが配置されている行を削除し、次に列j自体を削除します

選択した列にゼロ以外の要素があるすべての行は、ソリューションのこのブランチの構築に参加できなくなります。 つまり、位置Aと交差する（共通の正方形を持つ）コーナーのすべての位置を取り除きます。さらに、正方形24、33、34をすでにカバーしているため（行Aは既にスタック上にあります）、それらを処理する必要はありません。さらに、対応する列も削除されます。

ステップ5.縮小されたマトリックスでステップ1に進みます。

行と列を削除すると、小さなテーブルができました。 そして、ジオメトリの観点から、より小さな図形をカバーするタスクを取得しました。残りの線は、この図形の角の可能な位置に自動的に対応します。

アルゴリズム終了

手順1に進んだ後、特別な状況が発生する場合があります。



状況1.マトリックスに列が残っていないため、列を選択できません。 これは、使用可能なすべての正方形をカバーしたことを意味し、したがって、問題の解決策が見つかりました。 スタックの内容は、見つかったソリューションのリストに追加できます。



状況2.列を選択しましたが、最後の図の列44のように単一のユニットがありません。 これは、選択された正方形に対して、それをカバーできるコーナーの単一の位置がないことを意味します。 したがって、このブランチには解決策がありません。 この状況の特殊なケースは、マトリックスに行が残っていないことです。 手順1でユニットの数が最小の列を選択すると、表示されるとすぐに空の列が常に表示されることに注意してください。



アルゴリズムの反復のために1行と1列を意図的に取り除くため、行と列の数が減り、遅かれ早かれ状況1または状況2になります。

ダンシングリンク

アルゴリズムが迅速に機能するには、行列から行と列をすばやく削除できる必要があります。 行列を2次元配列の形式で保存する場合、これは非常に問題です。 一方、結果のマトリックスはほとんど常に非常にまばらです （特に、pentamino問題のマトリックスには4％単位しか含まれていません）。したがって、2次元の二重連結リストの形式で表現すると便利です。 このような表現により、行または列のすべての非ゼロ要素を最短時間で取得できます。



最後に、このようなリストを自由に使用できるので、列と行を削除し、ブランチに戻ってそれらを復元すると非常に便利です。

//   node->next->prev = node->prev; node->prev->next = node->next; //   node->next->prev = node; node->prev->next = node;
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この考えに基づいて、Knutのダンスリンク方法が基づいています。 （ちなみに、このメソッドの名前をGoogleの単数形の「ダンスリンク」に入力すると、ゼルダの伝説の主人公を含む多くのgifが写真に表示されます。）

パズルソリューション

元のパズルの最終的なソリューションコードは、 githubで表示できます（コードの大部分は、マトリックスの準備と、アイデンティティのソリューションをチェックする機能で占められています）。 私のラップトップでは、プログラムは5秒以内に4つの固有の解決策を見つけ（ターンや反射によって互いに縮小することはできません）、さらに50秒以内に他の解決策がないことを確認します。 実装がBurr Toolsソリューションよりも高速であることを認識できて良かったです。









アルゴリズムの最適化の1つは、キューブを覆うペンタアミノの2つの主要な位置（0、0、0）のみを残すことでした。他の可能な位置は回転と反射であるためです。 これにより、検索オプションの数が6倍に削減されました。 （実際、1つのポジションを離れるだけで十分ですが、これには追加の正当化が必要です）。



これ（および他のパズル）の解決策は、 puzzlewillbeplayed.comで見つけることができます。 そして最後まで読んだ人のために-アルゴリズムの一部の視覚化の形でのボーナス。 おそらく、このアニメーションは、アルゴリズムの名前の形容詞「ダンス」を正当化するでしょう。