Aritalab:Lecture/Algorithm/Sudoku - Revision history

Adm at 05:55, 22 August 2017

2017-08-22T05:55:21Z

Adm: /* Sudoku */

2017-08-22T05:46:16Z

‎Sudoku

Adm: /* Sudoku */

2017-08-22T04:15:31Z

‎Sudoku

Adm: /* Hitting Set */

2017-08-22T04:02:42Z

‎Hitting Set

Adm: /* Hitting Set */

2017-08-22T04:01:13Z

‎Hitting Set

Adm: /* Exact Cover by 3-Sets */

2011-10-12T16:10:53Z

‎Exact Cover by 3-Sets

Adm: /* Exact Cover by 3-Sets */

2011-10-12T16:07:22Z

‎Exact Cover by 3-Sets

Adm: moved Aritalab:Lecture/Programming/Java/AlgorithmX to Aritalab:Lecture/Algorithm/Sudoku

2011-10-12T16:06:21Z

moved Aritalab:Lecture/Programming/Java/AlgorithmX to Aritalab:Lecture/Algorithm/Sudoku

Adm: /* Hitting Set */

2011-10-04T05:05:55Z

‎Hitting Set

Adm at 05:08, 21 October 2010

2010-10-21T05:08:33Z

@@ Line 5: / Line 5: @@
 Algorithm Xは、KnuthがExact CoverというNP完全問題を力ずくで解くための全解探索ソルバーのことで、Dancing Linksと題された論文([http://arxiv.org/abs/cs/0011047 PDF at arXiv.org])で面白く紹介されています。
 ここではExact Cover, Hitting Setという問題の説明と、それを用いた数独の解法について解説します。
 ==Exact Cover==

@@ Line 66: / Line 66: @@
 ==Sudoku==
-ここで、数独が Exact Cover 問題に等しいことを示しましょう。
+ここで、数独が Hitting Set の部分問題であることを示しましょう。
 一般的な数独は 9 x 9 のマス目に 1 から 9 の数が入るので、9x9x9 = 729 個の選択肢があります。つまり、集合 S の要素が729個です。
 これらの要素は行を R, 列を C, 番号を # で表記すれば、(1,1,1) から (9,9,9) まで
@@ Line 97: / Line 97: @@
 制約には規則性があります。例えばマス (1,1) に 1 を入れる選択肢 R<sub>1</sub>C<sub>1</sub>#1 は、上記の制約のうち { R<sub>1</sub>C<sub>1</sub>, R<sub>1</sub>#1, C<sub>1</sub>#1, B<sub>1</sub>#1} という4つの制約に現れます。同様にすべての選択肢は、正確に4回ずつ、規則性を持って出現します。ただし、数独の問題で実際に数字が埋まっている部分は、選択肢の数が9個ではなく1個に減ります。
-数独は、Hitting Setとして解釈しなくても全解探索ですぐに解ける（[[Aritalab:Lecture/Programming/Java/Sudoku|Javaプログラム]]）のですが、理論的にはNP完全問題と同じ構造を持つということです。
+ただし 9 x 9 の数独は、Hitting Setとして解釈しなくても全解探索ですぐに解けます（[[Aritalab:Lecture/Programming/Java/Sudoku|Javaプログラム]]）。

@@ Line 67: / Line 67: @@
 ==Sudoku==
 ここで、数独が Exact Cover 問題に等しいことを示しましょう。
-一般的な数独は9x9の升目に1から9の数が入るので、9x9x9=729個の選択肢を持ちます。つまり、集合 S の要素が729個です。
+一般的な数独は 9 x 9 のマス目に 1 から 9 の数が入るので、9x9x9 = 729 個の選択肢があります。つまり、集合 S の要素が729個です。
-これらの要素は行をR, 列をC, 番号を#で表記すれば、(1,1,1)から(9,9,9)まで
+これらの要素は行を R, 列を C, 番号を # で表記すれば、(1,1,1) から (9,9,9) まで
 : R<sub>1</sub>C<sub>1</sub>#1, R<sub>1</sub>C<sub>1</sub>#2, …, R<sub>9</sub>C<sub>9</sub>#9
 の形に書けます。
-数独の制約は
+数独の制約は以下の 4 つです。
-; 各マスi, jに注目すると、1から9までの数字のどれか一つしか入らない
+<ol>
 : 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 &le; i, j &le; 9)
-; 各行iと数字nに注目すると、数字nは列1から列9までのどこかに入る
+<li> 各行 '''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 &le; i, n &le; 9)
-; 各列jと数字nに注目すると、数字nは行1から行9までのどこかに入る
+<li> 各列 '''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 &le; j, n &le; 9)
-; 9個ある3x3ボックスと数字nに注目すると、数字nは各ボックスのどこかに入る（例として左上のボックス）
+<li> 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 &le; n &le; 9)
-という4つに分けられます。制約の数は、上記の4制約それぞれについて9x9パターンあるので4 * 81 = 324通りです。
+上記の 4 制約それぞれが 9x9 パターンあるので、合計で 4 * 81 = 324 制約です。それぞれの制約として、729 個の選択肢からちょうど 9 個ずつ選ばれた Exact Hitting Set 問題になっています。
-つまり Exact Hitting Set 問題の例で 1～6 とあった制約が324個に増え、それぞれの制約にはちょうと9通りの選択肢があるのです。
-この問題設定は上記のHitting Setと同じですね。
-数独の制約には規則性があります。
+制約には規則性があります。例えばマス (1,1) に 1 を入れる選択肢 R<sub>1</sub>C<sub>1</sub>#1 は、上記の制約のうち { R<sub>1</sub>C<sub>1</sub>, R<sub>1</sub>#1, C<sub>1</sub>#1, B<sub>1</sub>#1} という4つの制約に現れます。同様にすべての選択肢は、正確に4回ずつ、規則性を持って出現します。ただし、数独の問題で実際に数字が埋まっている部分は、選択肢の数が9個ではなく1個に減ります。
-例えばマス(1,1)に1を入れる選択肢 R<sub>1</sub>C<sub>1</sub>#1 は、上記の制約のうち{ R<sub>1</sub>C<sub>1</sub>, R<sub>1</sub>#1, C<sub>1</sub>#1, B<sub>1</sub>#1} という4通りの制約に現れます。同様にすべての選択肢は、正確に4回ずつ規則性を持って出現します。ただし、数独の問題で実際に数字が埋まっている部分は、選択肢の数が9個ではなく1個になります。
 数独は、Hitting Setとして解釈しなくても全解探索ですぐに解ける（[[Aritalab:Lecture/Programming/Java/Sudoku|Javaプログラム]]）のですが、理論的にはNP完全問題と同じ構造を持つということです。

@@ Line 43: / Line 43: @@
 上の場合は　{A, D} という部分集合が、Exact Hitting Set になっています。この問題、実は、Exact Cover 問題に同じです。
-Exact Cover　における集合 X の各要素について、それを含む部分集合 C のラベルを集めた集合を作って S とおけばよいからです。
+Exact Cover　における集合 X の各要素について、それを含む部分集合 C のラベルを集めた集合を作っておけばよいからです。
 {| class="wikitable" style="width:200px"

@@ Line 31: / Line 31: @@
 ; 問題: Sの部分集合S', |S'| &le; K で、Cのどの部分集合とも少なくとも一つ重なる要素を持つものがあるか？
-この条件をきつくして、ちょうど一回だけ重なる要素を持つ、としたものが Exact Hitting Set です。
+この条件をきつくして、ちょうど一回だけ重なる要素を持つ、としたものが Exact Hitting Set と呼ばれる問題です。
-Exact Hitting Set 問題は、実は、Exact Cover 問題に同じです。
-Exact Cover　における集合 X の各要素について、それを含む部分集合 C のラベルを集めた集合を作って S とします。
 ; 例
@@ Line 44: / Line 42: @@
 * 6 = {<span style="color:red">D</span>, E};
+{| class="wikitable" style="width:200px"
 {|
-|valign="top"|上の Exact Cover と見比べてください。
-Exact Cover の要素集合 X が制約の集合に対応し、Exact Cover の制約 A～E が集合 S になっています。
-ここで {A, D} がHitting Setです。上記のExact Cover問題と全く同じ条件を読み替えている点を理解してみましょう。
-| <br/>'''どの列も行{A,D}<br/>(Exact Cover)で覆われる &rarr;'''
-−
-{| class="wikitable"
-|+ どの列も Hitting Set {A,D} を含む<br/>&darr;
 |-
 !   ||  1 || 2 || 3 || 4 || 5 || 6
 |-
 ! <span style="color:red">A</span>
-| * || * ||  || * ||  ||
+| ✖ || ✖ ||  || ✖ ||  ||
 |-
 ! B
-| * ||  || * || * ||  ||
+| ✖ ||  || ✖ || ✖ ||  ||
 |-
 ! C
-| * ||  || * ||  || * ||
+| ✖ ||  || ✖ ||  || ✖ ||
 |-
 ! <span style="color:red">D</span>
-|  ||  || * ||  || * || *
+|  ||  || ✖ ||  || ✖ || ✖
 |-
 ! E
-|  || * || * ||  ||  || *
+|  || ✖ || ✖ ||  ||  || ✖
-|}
 |}

@@ Line 6: / Line 6: @@
 ここではExact Cover, Hitting Setという問題の説明と、それを用いた数独の解法について解説します。
-==Exact Cover by 3-Sets==
+==Exact Cover==
 以下の組み合わせ問題を　Exact Cover　と呼びます。
-; 設定: 3の倍数ぶん要素を持つ集合Xと、要素の三つ組みの集合C
+; 設定: 集合Xと、Xの部分集合からなる集合C
 ; 問題: Cの部分集合 C'&sube;Cで、Xの要素が全てぴったり1回だけ現れるものがあるか？
-この問題は[[Aritalab:Lecture/Algorithm/Reducibility|3DMと呼ばれる問題と等価で、NP完全である]]ことが示されています。
+この問題は[[Aritalab:Lecture/Algorithm/Reducibility|3DMと呼ばれる問題を部分問題として含むため、NP完全である]]ことが示されています。
 ; 例

@@ Line 7: / Line 7: @@
 ==Exact Cover by 3-Sets==
-Exact Coverとは、以下の組み合わせ問題です。
+以下の組み合わせ問題を　Exact Cover　と呼びます。
 ; 設定: 3の倍数ぶん要素を持つ集合Xと、要素の三つ組みの集合C
@@ Line 16: / Line 16: @@
 ; 例
 集合 X = {1, 2, 3, 4, 5, 6};
-* A = {1, 2, 4};
+* A = <span style="color:red">{1, 2, 4};</span>
 * B = {1, 3, 4};
 * C = {1, 3, 5};
-* D = {3, 5, 6};
+* D = <span style="color:red">{3, 5, 6};</span>
 * E = {2, 3, 6};
-このうち、{A, D} がExact Coverになっています。
+このうち、AとDをあわせると、集合Xとちょうど一致するので {A, D} が Exact Cover になっています。
 ==Hitting Set==
-Hitting Setとは以下の組み合わせ問題です。
+以下の組み合わせ問題を Hitting Set と呼びます。
 ; 設定: 集合Sの部分集合の集合Cと、正の整数 K &le; |S|
 ; 問題: Sの部分集合S', |S'| &le; K で、Cのどの部分集合とも少なくとも一つ重なる要素を持つものがあるか？
-この条件をきつくして、ちょうど一回だけ重なる要素を持つ、としたものがExact Hitting Setです。
+この条件をきつくして、ちょうど一回だけ重なる要素を持つ、としたものが Exact Hitting Set です。
-Exact Hitting Set問題は、実は、Exact Cover問題に同じです。
+Exact Hitting Set 問題は、実は、Exact Cover 問題に同じです。
-Exact Coverにおける集合Xの各要素について、それを含む部分集合Cのラベルを集めた集合を作ってSとします。
+Exact Cover　における集合 X の各要素について、それを含む部分集合 C のラベルを集めた集合を作って S とします。
 ; 例
 集合 S = {A, B, C, D, E};
-* 1 = {A, B, C};
+* 1 = {<span style="color:red">A</span>, B, C};
-* 2 = {A, E};
+* 2 = {<span style="color:red">A</span>, E};
-* 3 = {B, C, D, E};
+* 3 = {B, C, <span style="color:red">D</span>, E};
-* 4 = {A, B};
+* 4 = {<span style="color:red">A</span>, B};
-* 5 = {C, D};
+* 5 = {C, <span style="color:red">D</span>};
-* 6 = {D, E};
+* 6 = {<span style="color:red">D</span>, E};
-ここで、{A, D}がHitting Setです。上記のExact Cover問題と全く同じ条件を読み替えている点を理解してみましょう。
 ==Sudoku==
-一般的な数独は9x9の升目に1から9の数が入るので、9x9x9=729個の選択肢を持ちます。
+ここで、数独が Exact Cover 問題に等しいことを示しましょう。
-これらの選択肢は行をR, 列をC, 番号を#で表記すれば、(1,1,1)から(9,9,9)まで
+一般的な数独は9x9の升目に1から9の数が入るので、9x9x9=729個の選択肢を持ちます。つまり、集合 S の要素が729個です。
 : R<sub>1</sub>C<sub>1</sub>#1, R<sub>1</sub>C<sub>1</sub>#2, …, R<sub>9</sub>C<sub>9</sub>#9
 の形に書けます。
@@ Line 64: / Line 69: @@
 という4つに分けられます。制約の数は、上記の4制約それぞれについて9x9パターンあるので4 * 81 = 324通りです。
-例えばマス(1,1)に1を入れる選択 R<sub>1</sub>C<sub>1</sub>#1 は、上記の制約のうちR<sub>1</sub>C<sub>1</sub>, R<sub>1</sub>#1, C<sub>1</sub>#1, B<sub>1</sub>#1 という4通りの制約に現れます。729ある選択肢が制約中に出現するパターンには対称性がありますが、数独の問題で実際に数字が埋まっている部分があれば、選択肢の数が9個ではなく1個になります。
+つまり Exact Hitting Set 問題の例で 1～6 とあった制約が324個に増え、それぞれの制約にはちょうと9通りの選択肢があるのです。
-この問題設定は上記のHitting Setと同じことがわかります。
+数独の制約には規則性があります。
 数独は、Hitting Setとして解釈しなくても全解探索ですぐに解ける（[[Aritalab:Lecture/Programming/Java/Sudoku|Javaプログラム]]）のですが、理論的にはNP完全問題と同じ構造を持つということです。