数学の分野である組合せ論において、集合の部分集合の集合が与えられたとき、の完全被覆とは の各要素が のちょうど1つの部分集合に含まれるような の部分集合のことである。の各要素はのちょうど1つの部分集合によって覆われていると言われる。[1]完全被覆は被覆 の一種である。言い換えれば、は に含まれる部分集合からなるの分割である。
完全被覆問題（完全被覆問題）は、制約充足問題の一種です。 の元は選択肢を表し、 の元は制約を表します。これはNP困難であり、航空便のフライトスケジュールの最適化、クラウドコンピューティング、電子回路設計など、様々な分野に応用されています。[2]
完全被覆問題は、部分集合と要素の間に関係「contains」が存在します。しかし、完全被覆問題は、選択肢の集合と制約の集合との間の任意の異種関係によって表現できます。例えば、完全被覆問題は、完全ヒット集合問題、接続行列、または二部グラフと同等です。
コンピュータサイエンスにおいて、完全被覆問題とは、完全被覆が存在するかどうかを判定する決定問題である。完全被覆問題はNP完全問題[3]であり、カープの21個のNP完全問題[4]の1つである。Sの各部分集合がちょうど3つの要素を含む場合でもNP完全である。この制限された問題は3集合による完全被覆問題として知られ、しばしばX3Cと略される。[3]
クヌースのアルゴリズムXは、完全被覆問題のすべての解を求めるアルゴリズムです。DLXは、ドナルド・クヌースのダンシング・リンクス技術を用いてコンピュータ上で効率的に実装されたアルゴリズムXに付けられた名前です。 [5]
正確なカバー問題は、正確に 1 回の制約だけでなく、最大で 1 回の制約も含むように若干一般化できます。
ペントミノタイルの探索や数独の解法は、完全被覆問題の注目すべき例です。nクイーン問題は、一般化された完全被覆問題です。
正式な定義
集合 の部分集合のコレクションが与えられたとき、 の完全被覆は次の 2 つの条件を満たす の部分コレクションです。
- における任意の2つの異なる部分集合の積集合は空である。すなわち、 における部分集合は互いに素である。言い換えれば、 における各要素は、における最大でも1つの部分集合にしか含まれない。
- の部分集合の和集合は であり、すなわち の部分集合は を覆う。言い換えれば、 の各要素はの少なくとも1つの部分集合に含まれる。
つまり、完全被覆は、の各要素が の 1 つのサブセットに正確に含まれているという意味で完全です。
同様に、 の正確な被覆はを分割するの部分集合です。
の正確な被覆が存在するためには、次のことが必要です。
- における部分集合の和集合はです。言い換えれば、 の各要素はにおける少なくとも1つの部分集合に含まれています。
空集合 が に含まれる場合、それが任意の完全被覆に含まれるかどうかは関係ありません。したがって、通常は次のように仮定します。
- 空集合は には存在しません。つまり、 の各部分集合には少なくとも1つの要素が含まれます。
基本的な例
を次 の集合の部分集合の集合とします。
- 、
- 、
- 、 そして
- 。
部分集合 とは互いに素であり、それらの和集合は であるため、の部分集合は の正確な被覆です。
部分集合も の完全被覆である。空集合はすべての部分集合と素であり、和集合も変わらないため、 空集合を含めても違いはない。
部分集合 はの完全被覆ではありません。 と の部分集合の和集合は ですが、 と、の積集合は空ではありません。したがって、 と の部分集合は完全被覆の 互いに素な条件を満たしていません。
部分集合も の正確な被覆ではありません。とは互いに素ですが、それらの和は ではないため、被覆要件を満たしていません。
一方、は の真部分集合であるため、 の正確な被覆は存在しません (実際には被覆さえありません) 。 のどの部分集合にも要素 5 は含まれません。
詳細な例
S = { A、B、C、D、E、F }を、集合X = {1、2、3、4、5、6、7} の部分集合の集合とします。
- A = {1, 4, 7};
- B = { 1 , 4 };
- C = {4, 5, 7};
- D = { 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はDと要素 3 と 6 を共有するため、Eは含まれません。この場合、F が唯一の部分集合となり、部分集合 { B , D , F } はまさに完全被覆となります。この議論の行列ベースのバージョンについては、 Knuth のアルゴリズム Xに関する記事の例を参照してください。
表現
完全被覆問題は、部分集合Sと要素 集合Xとの間の異種関係 containsによって定義されます。しかし、部分集合と要素には根本的な違いはありません。
完全被覆問題の表現は、選択肢の集合Sと制約の集合Xの間に異種関係R ⊆ S × Xがあり、 Xの各要素がS *のちょうど1つの要素とR T関連となるようなSの部分集合S *を選択することを目標としている場合に生じる。ここでR TはRの逆である。
一般に、R T を X × S *に制限すると、 XからS *への関数となり、Xの各要素を、その要素とR関係にあるS *の唯一の要素に写像します。この関数は、 S *にXのどの要素ともR関係のない要素（空集合に類似）が含まれていない限り、全射です。
正確なカバー問題の表現には、正確なヒットセット問題、接続行列、および二部グラフが含まれます。
正確な打撃セット
数学において、集合SとSの部分集合の集合Xが与えられたとき、 S の部分集合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 }
すると、S * = { b , d , f } は正確なヒットセットになります。これは、強調表示から明らかなように、 Xの各サブセットがS *の 1 つの要素にヒットする (含まれる) ためです。
この正確なヒット集合の例は、上記の詳細な例と本質的に同じです。要素から部分集合への関係が(∈)に含まれることを示すことで、文字付き部分集合を要素に、番号付き要素を部分集合に置き換えただけであることがわかります。
- 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の接続行列で表すことができます。
1 2 3 4 5 6 7 あ 1 0 0 1 0 0 1 B 1 0 0 1 0 0 0 C 0 0 0 1 1 0 1 D 0 0 1 0 1 1 0 E 0 1 1 0 0 1 1 F 0 1 0 0 0 0 1
ここでも、強調表示から明らかなように、各列には選択された行の 1 つにのみ 1 が含まれるため、 サブコレクションS * = { B , D , F } は完全被覆です。
上記の詳細な例に対する行列ベースのソリューションについては、 Knuth のアルゴリズム X の記事の例を参照してください。
ハイパーグラフ
同様に、接続行列はハイパーグラフを記述するものと見なすこともできます。ハイパーグラフには、Xの各要素に対して1つのノードと、 Sの各部分集合に対して1つのエッジが含まれます。各ノードは、被覆を形成するエッジの1つにのみ含まれます。
二部グラフ
関係contains は二部グラフで表すことができます。
グラフの頂点は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つの選択で満たされる可能性があるという可能性を許容することは、単純な一般化です。
クヌースが説明しているように、一般化完全被覆問題は、各二次列に1を1つずつ含む行を追加するだけで、同等の完全被覆問題に変換できます。[6]特定の候補解において特定の二次列が満たされている場合、追加された行は必要ありません。しかし、二次列が満たされていない場合（一般化問題では許容されますが標準問題では許容されません）、その列が満たされるように追加された行を選択できます。
しかし、Knuth 氏は、一般化されたアルゴリズムの方が単純かつ高速であるため、一般化された問題を直接扱う方がよいと説明しています。「アルゴリズム X に簡単な変更を加えるだけで、セカンダリ列を直接処理できるようになります。」
Nクイーン問題は、チェス盤の対角線に対応する制約に、正確なクイーン数ではなく最大値があるため、一般化された正確なカバー問題の例です。
注目すべき例
NP完全性により、NPのあらゆる問題は完全被覆問題に帰着することができ、Dancing Linksなどの手法を用いて解くことができます。しかし、よく知られている問題の中には、特に直接的に帰着できるものもあります。例えば、ペントミノで盤面をタイル張りする問題や数独を解く問題は、どちらも完全被覆問題として捉えることができます。
ペントミノタイリング
ドナルド・クヌースが論文「ダンシングリンク」で説明しているように、60マスのボードに12個の異なるフリーペントミノを敷き詰める問題は、正確な被覆問題の一例である。[5]
たとえば、中央の 4 つのマス目を取り除いた 8×8 のチェス盤をペントミノで敷き詰める問題を考えてみましょう。
11 12 13 14 15 16 17 18 21 22 23 24 25 26 27 28 31 32 33 34 35 36 37 38 41 42 43 46 47 48 51 52 53 56 57 58 61 62 63 64 65 66 67 68 71 72 73 74 75 76 77 78 81 82 83 84 85 86 87 88
この問題には 2 種類の制約が関係します。
- ペントミノ： 12個のペントミノそれぞれには、必ず1回だけ置かなければならないという制約があります。これらの制約を、対応するペントミノにちなんでFILPNTUVWXY Zと名付けましょう。[7]
- マス目: 60個のマス目それぞれに、ペントミノが必ず1回ずつ敷き詰められるという制約があります。これらの制約には、盤上の対応するマス目の名前（ij、iは階数、jはファイル）を付けてください。
したがって、制約は合計で 12+60 = 72 個あります。
どちらの種類の制約も正確に 1 回の制約であるため、問題は正確なカバー問題となります。
この問題には、ペントミノを盤上に配置する方法それぞれに1つずつ、多くの選択肢があります。それぞれの選択肢は、配置するペントミノに関する制約1つと、ペントミノが配置される5つのマスに関する制約5つ、合計6つの制約を満たすものと見なすのが便利です。
中央の 4 つのマス目を除いた 8×8 のチェス盤の場合、次のような 1568 通りの選択肢があります。
- {F、12、13、21、22、32}
- {F、13、14、22、23、33}
- …
- {1、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 個の選択肢のセットです。
- {1、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}
- {F、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つの数字しか入らないようにするためには必要です。当然ですが、あるセルに数字を入れると、そのセルに 他の数字を入れることはできなくなります。
数独を解くことは、完全被覆問題です。より正確には、数独を解くことは完全ヒットセット問題であり、これは、各制約集合が選択された可能性を1つだけ含む（つまり、ヒットする）ように可能性を選択する問題として捉えると、完全被覆問題と等価です。
特定の数字を特定のマス目に割り当てる可能性は、それぞれ可能性（または候補）と呼ばれます。鉛筆と紙を使って数独をプレイする場合、可能性はしばしば鉛筆マークと呼ばれます。
標準的な9×9の数独では、9×9のマス目に9つの数字が割り当てられており、9×9×9=729通りの可能性があります。行、列、数字の表記法を用いて、これらの可能性を次のように分類することができます。
- R1C1#1、R1C1#2、…、R9C9#9。
それぞれの制約条件が、何かの条件を一つだけ含むという事実こそが、数独を正確なヒットセット問題にしているのです。制約条件は制約セットで表現できます。問題は、各制約セットが選択された可能性を一つだけ含む（つまり、ヒットする）ように可能性を選択することです。
標準的な 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は、 1つの可能性からなる1x1×1の「立方体」です。さらに、各制約セットまたは可能性は、構成セットの交差です。たとえば、R1C2#3 = R1 ∩ C2 ∩ #3 です。ここで、∩ は積集合を表します。
他の数独のバリエーションでは、行数、列数、数字、および/または制約の種類が異なりますが、それらはすべて可能性と制約セットを伴うため、正確なヒットセット問題として見ることができます。
Nクイーン問題
Nクイーン問題とは、 n×nのチェス盤上にn個のクイーン を配置し、互いに脅威を与えないようにする問題です。解を得るには、同じ行、列、または対角線上に2つのクイーンが存在しないことが条件となります。これは、一般化された完全被覆問題の一例です。[5]
| 1つの | b | c | d | e | f | グラム | h | ||
| 8 |   | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| 1つの | b | c | d | e | f | グラム | h | ||
この問題には 4 種類の制約が関係します。
- ランク: Nランクごとに、クイーンが 1 つだけ存在する必要があります。
- ファイル: N個のファイルごとに、クイーンが 1 つだけ存在する必要があります。
- 対角線: 2 N − 1 個の対角線ごとに 、最大で 1 つのクイーンが存在する必要があります。
- 逆対角線: 2 N − 1 個の逆対角線ごとに 、クイーンが最大 1 個存在する必要があります。
2 N個の列と列が主制約を構成し、4 N − 2 個の対角線と逆対角線が副制約を構成します。さらに、最初の対角線、最後の対角線、逆対角線はそれぞれチェス盤上の1つのマス目のみに関係するため、これらを省略することができ、副制約の数を4 N − 6 個に減らすことができます。Nクイーン問題の行列はN 2行と6 N − 6 列で構成され、各行はチェス盤上の各マス目におけるクイーンの配置可能範囲を表し、各列は各制約を表します。
参照
- 制約充足問題
- ダンシングリンクス
- 差分マップアルゴリズム
- カープの21のNP完全問題
- クヌースのアルゴリズムX
- NP完全問題のリスト
- 集合の分割
- 完全マッチングと3次元マッチングは、正確な被覆問題の特殊なケースである。
参考文献
- ^ Solving Exact Cover Instances with Molecular-Motor-Powered Network-Based Biocomputation Pradheebha Surendiran、Christoph Robert Meinecke、Aseem Salhotra、Georg Heldt、Jingyuan Zhu、Alf Månsson、Stefan Diez、Danny Reuter、Hillel Kugler、Heiner Linke、Till Korten 2022 2 (5)、 396-403 DOI: 10.1021/acsnanoscienceau.2c00013
- ^ コルテン、ティル;ディエス、ステファン。リンケ、ハイナー。ニコラウ、ダン V;クグラー、ヒレル（2021-08-01）。 「正確なカバー問題のためのネットワークベースの生体計算回路の設計」。新しい物理学ジャーナル。23 (8): 085004。ビブコード:2021NJPh...23h5004K。土井：10.1088/1367-2630/ac175d。ISSN 1367-2630。
- ^ ab MR Garey、DS Johnson (1979). 『コンピュータとイントラクタビリティ：NP完全性理論へのガイド』ニューヨーク：WH Freeman. ISBN 0-7167-1045-5。 この本は理論を展開し、多くのNP 完全問題をカタログ化した古典です。
- ^ Richard M. Karp (1972). 「組合せ問題における縮約可能性」(PDF) . RE Miller, JW Thatcher (編).コンピュータ計算の複雑性. コンピュータ計算の複雑性に関するシンポジウム議事録. ニューヨーク: Plenum. pp. 85– 103. ISBN 0-3063-0707-3. 2011年6月29日時点のオリジナル（PDF）からアーカイブ。2008年6月27日閲覧。
- ^ abcde Knuth, Donald (2000). 「Dancing links」. arXiv : cs/0011047 .
- ^ ドナルド・クヌースは、論文「Dancing Links」の中で、特にテトラスティック問題とNクイーン問題を説明する際に、この単純な一般化を説明しています。
- ^ ゴロム、ソロモン・W. (1994). 『ポリオミノ：パズル、パターン、問題、そしてパッキング』（第2版）. プリンストン、ニュージャージー州: プリンストン大学出版局. p. 7. ISBN 0-691-02444-8。
- ^ Hanson, Robert M. 「Exact Cover Problem」. www.stolaf.edu . セント・オラフ大学. 2020年8月20日閲覧。
外部リンク
- C言語によるExact Coverソルバーのフリーソフトウェア実装。Algorithm XとDancing Linksを使用。数独とロジックグリッドパズルの例題も収録。
- Golangの完全カバーソルバー - アルゴリズムXとDancing Linksを使用。数独とNクイーンの例も含まれています。
- 正確なカバー - 数学リファレンスプロジェクト
- DLX 形式は、(色付きの) 正確なカバー問題を読み取るためにいくつかのソルバーで使用されます。
- Miniexactは、アルゴリズムX、C（色）、M（多重度）、そして初期段階では$（最小コスト）をサポートする、DLXの効率的で依存性のないC実装です。DLX形式とそのいくつかの拡張を読み込み、Pythonモジュールを提供します。PyPIから複数のプラットフォームにインストールできます。
