Aritalab:Lecture/Algorithm/Sudoku
(→Sudoku) |
m (→Sudoku) |
||
Line 49: | Line 49: | ||
数独の制約は | 数独の制約は | ||
− | + | ; 各マスi, jに注目すると、1から9までの数字のどれか一つしか入らない | |
: R<sub>i</sub>C<sub>j</sub> = { R<sub>i</sub>C<sub>j</sub>#1, R<sub>i</sub>C<sub>j</sub>#2, R<sub>i</sub>C<sub>j</sub>#3, ..., R<sub>i</sub>C<sub>j</sub>#9 }. (1 ≤ i, j ≤ 9) | : R<sub>i</sub>C<sub>j</sub> = { R<sub>i</sub>C<sub>j</sub>#1, R<sub>i</sub>C<sub>j</sub>#2, R<sub>i</sub>C<sub>j</sub>#3, ..., R<sub>i</sub>C<sub>j</sub>#9 }. (1 ≤ i, j ≤ 9) | ||
− | + | ||
+ | ; 各行iと数字nに注目すると、数字nは列1から列9までのどこかに入る | ||
: R<sub>i</sub>#n = { R<sub>i</sub>C<sub>1</sub>#n, R<sub>i</sub>C<sub>2</sub>#n, R<sub>i</sub>C<sub>3</sub>#n, ..., R<sub>i</sub>C<sub>9</sub>#n }. (1 ≤ i, n ≤ 9) | : R<sub>i</sub>#n = { R<sub>i</sub>C<sub>1</sub>#n, R<sub>i</sub>C<sub>2</sub>#n, R<sub>i</sub>C<sub>3</sub>#n, ..., R<sub>i</sub>C<sub>9</sub>#n }. (1 ≤ i, n ≤ 9) | ||
− | + | ||
+ | ; 各列jと数字nに注目すると、数字nは行1から行9までのどこかに入る | ||
: C<sub>j</sub>#n = { R<sub>1</sub>C<sub>j</sub>#n, R<sub>2</sub>C<sub>j</sub>#n, R<sub>3</sub>C<sub>j</sub>#n, ..., R<sub>9</sub>C<sub>j</sub>#n }. (1 ≤ j, n ≤ 9) | : C<sub>j</sub>#n = { R<sub>1</sub>C<sub>j</sub>#n, R<sub>2</sub>C<sub>j</sub>#n, R<sub>3</sub>C<sub>j</sub>#n, ..., R<sub>9</sub>C<sub>j</sub>#n }. (1 ≤ j, n ≤ 9) | ||
− | + | ||
+ | ; 9個ある3x3ボックスと数字nに注目すると、数字nは各ボックスのどこかに入る(例として左上のボックス) | ||
: B<sub>1</sub>#n = { R<sub>1</sub>C<sub>1</sub>#n, R<sub>1</sub>C<sub>2</sub>#n, R<sub>1</sub>C<sub>3</sub>#n, R<sub>2</sub>C<sub>1</sub>#n,R<sub>2</sub>C<sub>2</sub>#n, R<sub>2</sub>C<sub>3</sub>#n, R<sub>3</sub>C<sub>1</sub>#n,R<sub>3</sub>C<sub>2</sub>#n, R<sub>3</sub>C<sub>3</sub>#n }. (ボックスは9個; 1 ≤ n ≤ 9) | : B<sub>1</sub>#n = { R<sub>1</sub>C<sub>1</sub>#n, R<sub>1</sub>C<sub>2</sub>#n, R<sub>1</sub>C<sub>3</sub>#n, R<sub>2</sub>C<sub>1</sub>#n,R<sub>2</sub>C<sub>2</sub>#n, R<sub>2</sub>C<sub>3</sub>#n, R<sub>3</sub>C<sub>1</sub>#n,R<sub>3</sub>C<sub>2</sub>#n, R<sub>3</sub>C<sub>3</sub>#n }. (ボックスは9個; 1 ≤ n ≤ 9) | ||
Revision as of 12:45, 13 October 2010
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です。上記のExact Cover問題と全く同じ条件を読み替えている点を理解してみましょう。
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に注目すると、数字nは列1から列9までのどこかに入る
- Ri#n = { RiC1#n, RiC2#n, RiC3#n, ..., RiC9#n }. (1 ≤ i, n ≤ 9)
- 各列jと数字nに注目すると、数字nは行1から行9までのどこかに入る
- Cj#n = { R1Cj#n, R2Cj#n, R3Cj#n, ..., R9Cj#n }. (1 ≤ j, n ≤ 9)
- 9個ある3x3ボックスと数字nに注目すると、数字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つに分けられます。制約の数は、上記の4制約それぞれについて9x9パターンあるので4 * 81 = 324通りです。 例えばマス(1,1)に1を入れる選択 R1C1#1 は、上記の制約のうちR1C1, R1#1, C1#1, B1#1 という4通りの制約に現れます。729ある選択肢が制約中に出現するパターンには対称性がありますが、数独の問題で実際に数字が埋まっている部分があれば、選択肢の数が9個ではなく1個になります。
この問題設定は上記のHitting Setと同じことがわかります。
数独は、Hitting Setとして解釈しなくても全解探索ですぐに解ける(Javaプログラム)のですが、理論的にはNP完全問題と同じ構造を持つということです。