正確なカバー

数学の分野である組合せ論では、集合の部分集合のコレクションが与えられたとき、の各要素が のちょうど1 つの部分集合に含まれるようなの部分集合を完全被覆と呼んでいます。 の各要素は、 のちょうど 1 つの部分集合によって覆われているといいます。^{[1]完全被覆は}被覆 の一種です。これは非決定性多項式時間 (NP) 完全であり、航空会社のフライトスケジュールの最適化、クラウドコンピューティング、電子回路設計など、さまざまな用途に使用されています。^[2]${\displaystyle {\mathcal {S}}}$ ${\displaystyle X}$${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle {\mathcal {S}}}$${\displaystyle X}$${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle X}$ ${\displaystyle {\mathcal {S}}^{*}}$

言い換えると、は に含まれる部分集合からなるの分割です。 ${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle X}$${\displaystyle {\mathcal {S}}}$

正確なカバーを見つける正確なカバー問題は、制約充足問題の一種です。 の要素は選択肢を表し、 の要素は制約を表します。 ${\displaystyle {\mathcal {S}}}$${\displaystyle X}$

完全被覆問題には、部分集合と要素の関係が含まれます。ただし、完全被覆問題は、選択肢のセットと制約のセットの間の任意の異種関係によって表すことができます。たとえば、完全被覆問題は、完全ヒットセット問題、接続行列、または二部グラフと同等です。

コンピュータサイエンスにおいて、完全被覆問題とは、完全被覆が存在するかどうかを判断する決定問題である。完全被覆問題はNP完全^{[3]であり、}カープの21のNP完全問題^[4]の1つである。Sの各部分集合に3つの要素のみが含まれる場合でもNP完全である。この制限された問題は3集合による完全被覆と呼ばれ、しばしばX3Cと略される。^[3]

クヌースのアルゴリズムXは、正確な被覆問題のすべての解を見つけるアルゴリズムです。DLXは、ドナルド・クヌースのダンシング・リンクス技術を使用してコンピュータ上で効率的に実装されたアルゴリズムXに付けられた名前です。 ^[5]

正確なカバー問題は、正確に 1 回の制約だけでなく、最大で 1 回の制約も含むように若干一般化できます。

ペントミノのタイリングを見つけることや数独を解くことは、完全被覆問題の注目すべき例です。nクイーン問題は、一般化された完全被覆問題です。

集合 の部分集合のコレクションが与えられた場合、 の完全被覆は、次の 2 つの条件を満たすの部分コレクションです。 ${\displaystyle {\mathcal {S}}}$${\displaystyle X}$${\displaystyle X}$${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle {\mathcal {S}}}$

• 内の任意の 2 つの異なる部分集合の共通部分は空です。つまり、 内の部分集合は互いに素です。言い換えると、 内の各要素は、内の最大 1 つの部分集合に含まれています。${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle X}$${\displaystyle {\mathcal {S}}^{*}}$
• 内の部分集合の和集合は であり、すなわち 内の部分集合は をカバーします。言い換えると、 内の各要素は内の少なくとも 1 つの部分集合に含まれています。${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle X}$${\displaystyle {\mathcal {S}}^{*}}$ ${\displaystyle X}$${\displaystyle X}$${\displaystyle {\mathcal {S}}^{*}}$

つまり、完全被覆は、の各要素が の1つの部分集合に正確に含まれているという意味で完全です。 ${\displaystyle X}$${\displaystyle {\mathcal {S}}^{*}}$

同様に、 の完全被覆はを分割するの部分集合です。 ${\displaystyle X}$${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle {\mathcal {S}}}$ ${\displaystyle X}$

の正確な被覆が存在するためには、次のことが必要です。 ${\displaystyle X}$

• 内の部分集合の和集合は です。言い換えると、 内の各要素は内の少なくとも 1 つの部分集合に含まれています。${\displaystyle {\mathcal {S}}}$${\displaystyle X}$${\displaystyle X}$${\displaystyle {\mathcal {S}}}$

空集合 が に含まれている場合、それが任意の完全被覆内にあるかどうかは関係ありません。したがって、次のように仮定するのが一般的です。 ${\displaystyle \emptyset}$${\displaystyle {\mathcal {S}}}$

• 空集合は には存在しません。つまり、 の各サブセットには少なくとも 1 つの要素が含まれます。${\displaystyle {\mathcal {S}}^{*}}$${\displaystyle {\mathcal {S}}^{*}}$

次のような集合の部分集合の集合を とします。 ${\displaystyle {\mathcal {S}}=\{N,O,P,E\}}$${\displaystyle X=\{1,2,3,4\}}$

• ${\displaystyle N=\{\}}$、
• ${\displaystyle O=\{1,3\}}$、
• ${\displaystyle P=\{1,2,3\}}$、 そして
• ${\displaystyle E=\{2,4\}}$。

部分集合 と は互いに素であり、それらの和集合は であるため、 の部分集合は の完全被覆です。 ${\displaystyle \{O,E\}}$${\displaystyle X}$${\displaystyle O=\{1,3\}}$${\displaystyle E=\{2,4\}}$${\displaystyle X=\{1,2,3,4\}}$

部分集合も の完全被覆です。空集合はすべての部分集合と素であり、和集合は変わらないため、 空集合を含めても違いはありません。${\displaystyle \{N,O,E\}}$${\displaystyle X}$${\displaystyle N=\{\}}$

部分集合は の完全被覆ではありません。 部分集合 と の和集合はですが、部分集合と、の積集合は空ではありません。 したがって、部分集合と は完全被覆の 互いに素な要件を満たしていません。${\displaystyle \{E,P\}}$${\displaystyle X}$${\displaystyle E}$${\displaystyle P}$${\displaystyle \{1,2,3,4\}=X}$${\displaystyle E}$${\displaystyle P}$${\displaystyle \{2\}}$${\displaystyle E}$${\displaystyle P}$

部分集合も の正確な被覆ではありません。とは互いに素ですが、それらの和集合は ではないため、被覆要件を満たしていません。 ${\displaystyle \{N,P\}}$${\displaystyle X}$${\displaystyle N}$${\displaystyle P}$${\displaystyle X}$

一方、は の真部分集合であるため、の正確な被覆は存在しません (実際には被覆すら存在しません) 。 のどの部分集合にも要素 5 は含まれません。 ${\displaystyle Y=\{1,2,3,4,5\}}$${\displaystyle \bigcup {\mathcal {S}}=\{1,2,3,4\}}$${\displaystyle Y}$${\displaystyle {\mathcal {S}}}$

S = { A、B、C、D、E、F }を、集合X = {1、2、3、4、5、6、7} の部分集合の集合とします。

• 1 , 4, 7 です。
• 1から4までの整数。
• 4, 5, 7 の整数
• 3 , 5 , 6の整数部分
• E = {2, 3, 6, 7}; および
• F = { 2,7 }です。

部分集合S ^* = { B , D , F } は完全被覆です。強調表示から明らかなように、各要素は 1 つの選択された部分集合によって覆われる (含まれる) からです。

さらに、次の議論が示すように、 { B、D、F } が唯一の完全被覆です。 AとB は要素 1 を含む唯一の部分集合なので、完全被覆はAまたはB のいずれかを含む必要があり、両方を含むことはできません。完全被覆にAが含まれる場合、 B、C、E、またはF は含まれません。これらの各部分集合は、 Aと要素 1、4、または 7 を共有しているためです。するとD が唯一の残りの部分集合になりますが、部分集合 { A、D } は要素 2 をカバーしません。結論として、A を含む完全被覆は存在しません。一方、完全被覆にBが含まれる場合、 AまたはC は含まれません。これらの各部分集合は、 Bと要素 1 または 4 を共有しているためです。D は要素 5 を含む唯一の残りの部分集合なので、D は完全被覆の一部でなければなりません。完全被覆にD が含まれる場合、 Eは含まれません。これは、E がDと共通する要素 3 と 6 を持っているためです。この場合、F が唯一の残りの部分集合となり、部分集合 { B、D、F } は確かに完全被覆です。この議論の行列ベースのバージョンについては、 Knuth のアルゴリズム Xに関する記事の例を参照してください。

完全被覆問題は、部分集合の集合Sと要素の集合Xとの間の異種関係 によって定義されます。しかし、部分集合と要素には根本的なものは何もありません。

完全被覆問題の表現は、選択肢の集合Sと制約の集合Xの間に異種関係R ⊆ S × Xがあり、 Xの各要素がS ^*のちょうど 1 つの要素とR ^T関連になるようにSのサブセットS ^{* を}選択することが目標である場合に発生します。ここで、R ^{T は}Rの逆です。

一般に、R ^{T を} X × S ^*に制限すると、 XからS ^*への関数となり、Xの各要素を、 Xのその要素にR関連のS ^*の一意の要素にマッピングします。 S ^*にXのどの要素にもR関連の無い要素（空集合に類似）が含まれていない限り、この 関数は上に写像されます。

正確なカバー問題の表現には、正確なヒットセット問題、接続行列、および二部グラフが含まれます。

数学では、集合SとSの部分集合のコレクションXが与えられたとき、正確にヒットする集合S ^*は、 Xの各部分集合にS ^*の要素が1 つだけ含まれるようなSの部分集合です。つまり、 Xの各部分集合はS ^*の要素の 1 つにヒットすると言えます。

正確なヒット セット問題は、が含まれるのではなくに含まれるという関係を含む正確なカバー問題の表現です。

たとえば、S = { a、b、c、d、e、f } を集合とし、X = { I、II、III、IV、V、VI、VII } をSのサブセットのコレクションとすると、次のようになります。

• 私は= { a , b }
• II = { e , f }
• III = { d、e }
• IV = { a、b、c }
• V = { c , d }
• VI = { d , e }
• VII = { a、c、e、f }

すると、強調表示から明らかなように、 Xの各サブセットはS ^*の要素を 1 つだけヒットする (含む)ため、 S ^* = { b , d , f } は正確なヒット セットになります。

この正確なヒットセットの例は、基本的に上記の詳細な例と同じです。要素からサブセットへの関係is contains (∈) を表示すると、文字付きサブセットを要素に、番号付き要素をサブセットに置き換えただけであることがわかります。

• a ∈ I、IV、VII ;
• b∈I , IV ;​​
• c∈IV、V、VII ;​​
• d ∈ III、 V、 VI ;
• e ∈ II、III、VI、VII ;そして
• f∈ II、 VII。​

関係は接続行列によって表すことができます。

行列には、 Sの各サブセットに対して 1 行、 Xの各要素に対して 1 列が含まれます。特定の行と列のエントリは、対応するサブセットに対応する要素が含まれている場合は 1 になり、それ以外の場合は 0 になります。

行列表現では、正確なカバーとは、各列に 1 つの選択された行に 1 が含まれる行の選択です。各行は選択を表し、各列は制約を表します。

たとえば、上記の詳細な例に含まれる関係は、6×7 の接続行列で表すことができます。

繰り返しになりますが、部分集合S ^* = { B , D , F } は完全被覆です。強調表示から明らかなように、各列には選択された行の 1 つに 1 が含まれているからです。

上記の詳細な例に対する行列ベースのソリューションについては、 Knuth のアルゴリズム Xに関する記事の例を参照してください。

同様に、接続行列はハイパーグラフを記述するものとみなすこともできます。ハイパーグラフには、 Xの各要素に対して 1 つのノードと、Sの各サブセットに対して 1 つのエッジが含まれます。各ノードは、カバーを形成するエッジの 1 つにのみ含まれます。

関係は二部グラフで表すことができます。

グラフの頂点は 2 つの互いに素な集合に分割され、1 つはS内のサブセットを表し、もう 1 つはX内の要素を表します。サブセットに要素が含まれている場合、エッジはグラフ内の対応する頂点を接続します。

グラフ表現において、正確なカバーとは、要素に対応する各頂点が正確に 1 つの選択された頂点に接続されるような、サブセットに対応する頂点の選択です。

たとえば、上記の詳細な例に 含まれる関係は、6 + 7 = 13 個の頂点を持つ二部グラフで表すことができます。

また、部分集合S ^* = { B , D , F } は、強調表示によって明らかなように、 X内の各要素に対応する頂点が正確に 1 つの選択された頂点に接続されているため、完全被覆です。

アルゴリズムXは、ドナルド・クヌースが、正確な被覆問題に対するすべての解を見つけるための「最も明白な試行錯誤のアプローチ」に付けた名前です。 ^{[5]技術的には、アルゴリズムXは}再帰的、非決定的、深さ優先、バックトラッキング アルゴリズムです。

アルゴリズム X がドナルド・クヌースのダンシングリンク技法を使用してコンピュータ上で効率的に実装されると、クヌースはそれを DLX と呼びます。これは問題の行列表現を使用し、行列の 1 の二重リンクリストのシリーズとして実装されます。各 1 要素には、その上、下、左、右にある次の 1 へのリンクがあります。正確なカバー問題はまばらになる傾向があるため、この表現は通常、必要なサイズと処理時間の両方ではるかに効率的です。次に DLX はダンシングリンク技法を使用して、可能な解として行の順列をすばやく選択し、誤った推測を効率的にバックトラック (元に戻す) します。^[5]

標準的な完全カバー問題では、各制約は正確に 1 回満たされる必要があります。この要件を少し緩和し、いくつかの主要な制約は正確に 1 つの選択で満たされる必要があるが、他の二次制約は最大で 1 つの選択で満たされる可能性があると認めることは、単純な一般化です。

Knuth が説明しているように、一般化された完全被覆問題は、各二次列に 1 つの 1 を含む行を 1 つ追加するだけで、同等の完全被覆問題に変換できます。^[6]特定の候補ソリューションで特定の二次列が満たされている場合、追加された行は必要ありません。ただし、二次列が満たされていない場合 (一般化問題では許可されていますが標準問題では許可されていません)、列が満たされるように追加された行を選択できます。

しかし、Knuth 氏は、一般化されたアルゴリズムの方が単純で高速であるため、一般化された問題を直接扱う方がよいと説明しています。アルゴリズム X に簡単な変更を加えるだけで、セカンダリ列を直接処理できるようになります。

Nクイーン問題は、チェス盤の対角線に対応する制約が正確なクイーン数ではなく最大値を持つため、一般化された正確なカバー問題の例です。

NP 完全性により、NP のあらゆる問題は完全被覆問題に還元することができ、Dancing Links などの手法で解決できます。ただし、よく知られている問題の中には、還元が特に直接的なものもあります。たとえば、ペントミノでボードをタイル張りする問題や、数独を解く問題は、どちらも完全被覆問題として考えることができます。

ドナルド・クヌースが論文「ダンシング・リンク」で説明しているように、60マスのボードに12個の異なる自由ペントミノを並べる問題は、完全被覆問題の一例である。^[5]

たとえば、中央の 4 つのマス目を取り除いた 8×8 のチェス盤をペントミノで並べる問題を考えてみましょう。

この問題には 2 種類の制約が関係します。

ペントミノ： 12個のペントミノのそれぞれには、必ず1回だけ配置しなければならないという制約があります。これらの制約を、対応するペントミノにちなんで命名します：FILPNTUVWXY Z。^[7]

正方形: 60 個の正方形のそれぞれには、ペントミノで 1 回だけ覆われるという制約があります。ボード内の対応する正方形にちなんで、これらの制約にij という名前を付けます。ここで、iはランク、j はファイルです。

したがって、制約は全部で 12+60 = 72 個あります。

どちらの種類の制約も正確に 1 回の制約であるため、問題は正確なカバー問題です。

この問題には、ペントミノをボード上に配置する方法ごとに 1 つずつ、多数の選択肢があります。各選択肢は、配置するペントミノに関する制約 1 つと、ペントミノを配置する 5 つのマス目に関する制約 5 つ、合計 6 つの制約を満たすものと考えると便利です。

中央の 4 つのマス目を除いた 8×8 のチェス盤の場合、次のような選択肢が 1568 通りあります。

• {女性、12、13、21、22、32}
• {女性、13、14、22、23、33}
• …
• {I、11、12、13、14、15}
• {1、12、13、14、15、16}
• …
• {L、11、21、31、41、42}
• {L、12、22、32、42、43}
• …

この正確なカバー問題に対する多くの解決策の 1 つは、次の 12 個の選択肢のセットです。

• {I、11、12、13、14、15}
• {N、16、26、27、37、47}
• {L、17、18、28、38、48}
• {U、21、22、31、41、42}
• {X、23、32、33、34、43}
• {W、24、25、35、36、46}
• {P、51、52、53、62、63}
• {女性、56、64、65、66、75}
• {Z、57、58、67、76、77}
• {T、61、71、72、73、81}
• {V、68、78、86、87、88}
• {Y、74、82、83、84、85}

この選択セットは、ペントミノタイリング問題に対する次の解決策に対応します。

ペントミノタイリング問題は、正確なヒットセット問題よりも正確なカバー問題として捉えるのが自然です。これは、各制約を選択肢のセットとして捉えるよりも、各選択肢を制約のセットとして捉える方が自然だからです。

それぞれの選択肢は 6 つの制約にのみ関連しており、列挙するのは簡単です。一方、それぞれの制約は多くの選択肢に関連しており、列挙するのは困難です。

正確なカバー問題として見ても、正確なヒット セット問題として見ても、行列表現は同じで、選択肢に対応する 1568 行と制約に対応する 72 列があります。各行には、ペントミノを識別する列に 1 つの 1 が含まれ、ペントミノでカバーされるマス目を識別する列に 5 つの 1 が含まれます。

マトリックスを使用すると、コンピューターは、たとえばDancing Links を使用して、すべてのソリューションを比較的迅速に見つけることができます。

 主な記事:数独、数独の数学、数独を解くアルゴリズム

数独の問題は、特定の制約を満たすように、グリッド内のセル（または四角形）に数字（または数字、値、記号）を割り当てることです。

標準的な 9×9 数独のバリエーションには、次の 4 種類の制約があります。

行と列: 行と列の交差部分、つまり各セルには、必ず 1 つの数字が含まれている必要があります。

行番号: 各行には、各番号が 1 つずつ含まれている必要があります。

列番号: 各列には、各番号が 1 つずつ含まれている必要があります。

ボックス番号: 各ボックスには、各番号が 1 つずつ含まれている必要があります。

最初の制約は些細なことのように思えるかもしれませんが、セルごとに 1 つの数字だけが存在することを保証するために必要です。当然、セルに数字を配置すると、現在占有されているセルに 他の数字を配置することは禁止されます。

数独を解くことは、正確なカバー問題です。より正確には、数独を解くことは正確な​​ヒットセット問題であり、各制約セットが正確に 1 つの選択された可能性を含む (つまり、ヒットする) ように可能性を選択する問題として見ると、正確なカバー問題と同等です。

特定の数字を特定のセルに割り当てることができる可能性は、それぞれ可能性(または候補) です。鉛筆と紙を使って数独をプレイする場合、可能性は鉛筆マークと呼ばれることがよくあります。

標準的な9×9の数独では、9×9のマス目に9つの数字が割り当てられており、9×9×9=729通りの可能性がある。行、列、数字の明確な表記法を使用して、可能性をラベル付けすることができる。

R1C1#1、R1C1#2、…、R9C9#9。

それぞれの種類の制約が何かのちょうど 1 つを含むという事実は、数独が正確なヒット セット問題である理由です。制約は制約セットで表すことができます。問題は、各制約セットが選択された可能性をちょうど 1 つ含む (つまり、ヒットする) ように可能性を選択することです。

標準的な 9×9 数独のバリエーションでは、4 種類の制約に対応する 4 種類の制約セットがあります。

行-列:行-列制約セットには、特定の行と列、つまりセルの交差の可能性がすべて含まれています。たとえば、行 1 と列 1 の制約セット (ラベルは R1C1) には、行 1 と列 1 の 9 つの可能性が含まれていますが、その数は異なります。

R1C1 = { R1C1#1、R1C1#2、R1C1#3、R1C1#4、R1C1#5、R1C1#6、R1C1#7、R1C1#8、R1C1#9 }。

行番号:行番号制約セットには、特定の行と番号のすべての可能性が含まれます。たとえば、行 1 と番号 1 の制約セット (ラベルは R1#1) には、行 1 と番号 1 の異なる列の 9 つの可能性が含まれます。

R1#1 = {R1C1#1、R1C2#1、R1C3#1、R1C4#1、R1C5#1、R1C6#1、R1C7#1、R1C8#1、R1C9#1 }。

列番号:列番号制約セットには、特定の列と番号のすべての可能性が含まれます。たとえば、列 1 と番号 1 の制約セット (ラベルは C1#1) には、列 1 と番号 1 の 9 つの可能性が含まれますが、行は異なります。

C1#1 = { R1C1#1、R2C1#1、R3C1#1、R4C1#1、R5C1#1、R6C1#1、R7C1#1、R8C1#1、R9C1#1 }。

ボックス番号:ボックス番号制約セットには、特定のボックスと番号のすべての可能性が含まれます。たとえば、ボックス 1 (左上隅) と番号 1 (B1#1 というラベルが付けられる) の制約セットには、ボックス 1 と番号 1 のセルの 9 つの可能性が含まれます。

B1#1 = { R1C1#1、R1C2#1、R1C3#1、R2C1#1、R2C2#1、R2C3#1、R3C1#1、R3C2#1、R3C3#1 }。

9 行、9 列、9 ボックス、9 個の数字があるため、行-列制約セットは 9×9=81 個、行番号制約セットは 9×9=81 個、列番号制約セットは 9×9=81 個、ボックス番号制約セットは 9×9=81 個あり、合計で 81+81+81+81=324 個の制約セットになります。

簡単に言うと、標準的な 9×9 数独のバリエーションは、729 の可能性と 324 の制約セットを持つ正確なヒットセット問題です。したがって、この問題は 729×324 の行列で表すことができます。

729×324 マトリックス全体を表示することは困難ですが、いくつかのスナップショットからマトリックスの一般的な性質を確認できます。

完全な729×324マトリックスはロバート・ハンソンから入手可能です。^[8]

可能性の集合 R x C y # z は、座標x、y、zを持つ 3 次元空間に 9×9×9 の立方体として配置できることに注目してください。この場合、各行 R x、列 C y、または番号 # zは、可能性の 9×9×1 の「スライス」です。各ボックス B wは、可能性の 9x3×3 の「チューブ」です。各行列制約集合 R x C y、行番号制約集合 R x # z、または列番号制約集合 C y # zは、可能性の 9x1×1 の「ストリップ」です。各ボックス番号制約集合 B w # zは、可能性の 3x3×1 の「正方形」です。各可能性 R x C y # z は、単一の可能性からなる 1x1×1 の「立方体」です。さらに、各制約集合または可能性は、コンポーネント集合の交差です。たとえば、R1C2#3 = R1 ∩ C2 ∩ #3 であり、ここで ∩ は集合の交差を表します。

他の数独のバリエーションでは、行数、列数、数字、および/または制約の種類が異なりますが、それらはすべて可能性と制約セットを伴うため、正確なヒットセット問題として見ることができます。

Nクイーン問題とは、 n×nのチェス盤にn個のクイーン を配置し、2つのクイーンが互いに脅威にならないようにする問題である。解決するには、2つのクイーンが同じ行、列、または対角線を共有しないようにする必要がある。これは一般化された完全被覆問題の例である。^[5]

この問題には 4 種類の制約が関係します。

ランク: Nランクごとに、クイーンが 1 つだけ存在する必要があります。

ファイル: N個のファイルごとに、クイーンが 1 つだけ存在する必要があります。

対角線: 2 N − 1 個の対角線ごとに 、最大で 1 つのクイーンが存在する必要があります。

逆対角線: 2 N  − 1 個の逆対角線ごとに、クイーンは最大 1 個存在する必要があります。

2 N のランクとファイルが主要な制約を形成し、4 N  − 2 の対角線と逆対角線が二次制約を形成することに注意してください。さらに、最初の対角線と最後の対角線、逆対角線はそれぞれチェス盤の 1 つのマス目のみに関係するため、これらを省略して二次制約の数を 4 N  − 6 に減らすことができます。N クイーン問題のマトリックスにはN ²行と 6 N  − 6 列があり、各行はチェス盤の各マス目のクイーンの配置可能範囲、各列は各制約を表します。

• 制約充足問題
• ダンスリンク
• 差分マップアルゴリズム
• カープの21のNP完全問題
• クヌースのアルゴリズムX
• NP完全問題のリスト
• 集合の分割
• 完全マッチングと3次元マッチングは、完全被覆問題の特殊なケースである。

• C 言語による Exact Cover ソルバーのフリー ソフトウェア実装 - Algorithm X と Dancing Links を使用。数独とロジック グリッド パズルの例が含まれています。
• Golang の Exact Cover ソルバー - アルゴリズム X と Dancing Links を使用します。数独と N クイーンの例が含まれています。
• 正確なカバー - 数学リファレンスプロジェクト