NTK理論の論文による概要把握作業が一息ついたのでTACOPにもどる
序の章でのXCC(extruct cover problem) の話でインターネットを探しまくる
スタンフォードのCWEBのPG
Exact Cover Problem とそれを応用した数独解読アルゴリズム
Dancing Linksを用いたKnuth's Algorithm Xによる数独ソルバーの実装
rafalio/dancing-links-java (GitHub)
例として 数独
Knuth's Algorithm X
Dancing Links
Donald E. Knuth, Stanford University 論文
Knuth's Algorithm XとDancing Linksの解説
Exact Cover Problem and Algorithm X
Efficient Algorithm for Enumerating All Solutions to an Exact Cover Problem
NTT technical review
Python for education :the extract cover problem
最後に wikipedia で Exact cover を調べると NP-COMLETE とあった
Exact CoverがN Pであることが簡単にわかります。
N P完全であることを証明するために、充足可能性問題をこれに還元します。
これは、充足可能性問題のすべてのインスタンスを完全カバーのインスタンスに変換す
る多項式時間で実行されるメソッドを提供することを意味します。
変換された問題に解決策がある場合、最初の問題には解決策があります。
