ダンスのつながり

DLX のアイデアは、ノードの円形二重リンクリストにおいて、

x.left.right ← x.right; x.right.left ← x.left;

リストからノードxを削除しますが、

x.left.right ← x; x.right.left ← x;

x.rightとx.leftが変更されていないことを前提として、リスト内のxの位置を復元します。これは、リスト内の要素数に関係なく機能します。要素数が1の場合でも同様です。

クヌースは、自身のアルゴリズムXを単純に実装すると、1を探すのに膨大な時間を費やすことに気づきました。列を選択する際には、行列全体から1を探す必要がありました。行を選択する際には、列全体から1を探す必要がありました。行を選択した後は、その行と複数の列から1を探す必要がありました。この検索時間をO(n)の複雑さからO(1)に改善するために、クヌースは1のみを格納する疎行列を実装しました。

行列内の各ノードは、常に左右の隣接ノード（同じ行の1）、上下の隣接ノード（同じ列の1）、およびその列のヘッダー（後述）を指します。行列の各行と各列は、ノードの循環二重リンクリストで構成されます。

各列には「列ヘッダー」と呼ばれる特別なノードがあり、これは列リストに含まれ、マトリックス内に残っているすべての列で構成される特別な行（「制御行」）を形成します。

最後に、各列ヘッダーは、その列内のノード数を追跡するようにオプションで設定できます。これにより、ノード数が最も少ない列を見つける際の計算量は、列数 n と行数 m に対して、O(n × m) ではなく O(n) となります。ノード数の少ない列を選択することは、場合によってはパフォーマンスを向上させるヒューリスティックですが、アルゴリズムに必須ではありません。

アルゴリズム X では、行と列が定期的に行列から削除され、復元されます。削除は、列とその列内の行を選択することによって決定されます。選択された列に行がない場合、現在の行列は解けず、バックトラックする必要があります。削除が発生すると、選択された行に 1 が含まれるすべての列と、削除された列のいずれかに 1 が含まれるすべての行 (選択された行を含む) が削除されます。列は既にデータが入力されているため削除され、行は選択された行と競合するため削除されます。単一の列を削除するには、まず選択された列のヘッダーを削除します。次に、選択された列に 1 が含まれる各行について、その行を走査し、他の列から削除します (これにより、それらの行にアクセスできなくなり、競合が防止されます)。選択された行に 1 が含まれる各列について、この列の削除を繰り返します。この順序により、削除されたノードは正確に 1 回、かつ予測可能な順序で削除されるため、適切にバックトラックできます。結果として得られる行列に列がない場合、すべての列が埋められており、選択された行が解となります。

バックトラックを行うには、上記のプロセスを、前述の2番目のアルゴリズムを使用して逆方向に実行する必要があります。このアルゴリズムを使用する際の要件の1つは、バックトラックが削除の正確な逆操作として実行されなければならないことです。クヌースの論文は、これらの関係とノードの削除および再挿入の仕組みを明確に示し、この制約をわずかに緩和しています。

特定の制約がオプションであるが、一度しか満たせないワンカバー問題を解くことも可能です。ダンシングリンクは、必ず埋めなければならないプライマリ列とオプションのセカンダリ列でこれらに対応します。これにより、アルゴリズムの解のテストが、列のない行列からプライマリ列のない行列に変更され、列内の最小の 1 というヒューリスティックが使用されている場合は、プライマリ列内でのみチェックする必要があります。クヌースは、nクイーン問題に適用されるオプション制約について議論しています。チェス盤の対角線はオプション制約を表しており、一部の対角線は占有されない可能性があります。対角線が占有されている場合、それは一度しか占有できません。