Exact Cover Problem 今回解説するKnuth's Algorithm Xは、Exact Cover Problemという問題を解くためのアルゴリズムです。Exact Cover Problemについてはうまい日本語訳が分からない(「敷き詰め問題」とか?)ので英語のまま書いています。 数学で言うと、ある集合Xの部分集合の集合Sが与えられて、そのSの部分集合であるようなS*において、Xに含まれる要素全てがS*の中にひとつだけ含まれるとき、S*はExact Coverであると言います。 ちょっと分かりづらいと思うので具体例を挙げると、まず集合 X = {1, 2, 3, 4, 5} だとします。そして集合 S = {A, B, C, D, E, F} として、A,B,C,D,E,Fは以下のようであるとします。 A = {1, 3} B = {1, 4, 5} C = {2, 4