Aritalab:Lecture/Algorithm/Sudoku
Contents |
KnuthのアルゴリズムX
Donald KnuthはTeXの開発者、"The Art of Programming"の著者で、様々なアルゴリズムも開発した著名な計算機科学者です。 Algorithm Xは、KnuthがExact CoverというNP完全問題を力ずくで解くための全解探索ソルバーのことで、Dancing Linksと題された論文(PDF at arXiv.org)で面白く紹介されています。 ここではExact Cover, Hitting Setという問題の説明と、それを用いた数独の解法について解説します。
Exact Cover by 3-Sets
Exact Coverとは、以下の組み合わせ問題です。
- 設定
- 3の倍数ぶん要素を持つ集合Xと、要素の三つ組みの集合C
- 問題
- Cの部分集合 C'⊆Cで、Xの要素が全てぴったり1回だけ現れるものがあるか?
この問題は3DMと呼ばれる問題と等価で、NP完全であることが示されています。
- 例
集合 X = {1, 2, 3, 4, 5, 6};
- A = {1, 2, 4};
- B = {1, 3, 4};
- C = {1, 3, 5};
- D = {3, 5, 6};
- E = {2, 3, 6};
このうち、{A, D} がExact Coverになっています。
Hitting Set
Hitting Setとは以下の組み合わせ問題です。
- 設定
- 集合Sの部分集合の集合Cと、正の整数 K ≤ |S|
- 問題
- Sの部分集合S', |S'| ≤ K で、Cのどの部分集合とも少なくとも一つ重なる要素を持つものがあるか?
この条件をきつくして、ちょうど一回だけ重なる要素を持つ、としたものがExact Hitting Setです。 Exact Hitting Set問題は、実は、Exact Cover問題に同じです。 Exact Coverにおける集合Xの各要素について、それを含む部分集合Cのラベルを集めた集合を作ってSとします。
- 例
集合 S = {A, B, C, D, E};
- 1 = {A, B, C};
- 2 = {A, E};
- 3 = {B, C, D, E};
- 4 = {A, B};
- 5 = {C, D};
- 6 = {D, E};
ここで、{A, D}がHitting Setです。
Sudoku
一般的な数独は9x9の升目に1から9の数が入るので、9x9x9=729通りの可能性があります。 全てのパターンは行をR, 列をC, 番号を#で表記すれば、(1,1,1)から(9,9,9)まで
- R1C1#1, R1C1#2, …, R9C9#9
の形に書けます。
数独の制約は
- 全てのマスi, jにおいて、1から9までの数字のどれか一つしか入らない
- RiCj = { RiCj#1, RiCj#2, RiCj#3, ..., RiCj#9 }. (1 ≤ i, j ≤ 9)
- 全ての行iと数字nにおいて、
- Ri#n = { RiC1#n, RiC2#n, RiC3#n, ..., RiC9#n }. (1 ≤ i, n ≤ 9)
- 全ての列jと数字nにおいて、
- Cj#n = { R1Cj#n, R2Cj#n, R3Cj#n, ..., R9Cj#n }. (1 ≤ j, n ≤ 9)
- 全ての3x3ボックスと数字nにおいて、(例として左上のボックス)
- B1#n = { R1C1#n, R1C2#n, R1C3#n, R2C1#n,R2C2#n, R2C3#n, R3C1#n,R3C2#n, R3C3#n }. (ボックスは9個; 1 ≤ n ≤ 9)
と書けます。制約の数は、上記の4制約全てについて9x9パターンあるので4 * 81 = 324通りです。 例えばマス(1,1)に1を入れる選択 R1C1#1 は、上記の制約のうちR1C1, R1#1, C1#1, B1#1 という4通りの制約に現れます。729ある選択肢が制約中に出現するパターンには対称性がありますが、数独の問題で実際に数字が埋まっている部分があれば、選択肢の数が9個ではなく1個になります。
この問題設定は上記のHitting Setになることがわかります。