Aritalab:Lecture/Algorithm/Sudoku

Latest revision as of 14:55, 22 August 2017

[edit] 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という問題の説明と、それを用いた数独の解法について解説します。

Algorithm X の Javaコード
Algorithm X より速い簡単なバックトラック Sudoku solver Javaコード

[edit] Exact Cover

以下の組み合わせ問題を　Exact Cover　と呼びます。

設定: 集合Xと、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をあわせると、集合Xとちょうど一致するので {A, D} が Exact Cover になっています。　この例では、 {A, D} 以外の Exact Cover はありません。

[edit] Hitting Set

以下の組み合わせ問題を Hitting Set と呼びます。

設定: 集合Sの部分集合の集合Cと、正の整数 K ≤ |S|
問題: Sの部分集合S', |S'| ≤ K で、Cのどの部分集合とも少なくとも一つ重なる要素を持つものがあるか？

この条件をきつくして、ちょうど一回だけ重なる要素を持つ、としたものが Exact Hitting Set と呼ばれる問題です。

例

集合 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} という部分集合が、Exact Hitting Set になっています。この問題、実は、Exact Cover 問題に同じです。 Exact Cover　における集合 X の各要素について、それを含む部分集合 C のラベルを集めた集合を作っておけばよいからです。

	1	2	3	4	5	6
A	✖	✖		✖
B	✖		✖	✖
C	✖		✖		✖
D			✖		✖	✖
E		✖	✖			✖

[edit] Sudoku

ここで、数独が Hitting Set の部分問題であることを示しましょう。一般的な数独は 9 x 9 のマス目に 1 から 9 の数が入るので、9x9x9 = 729 個の選択肢があります。つまり、集合 S の要素が729個です。これらの要素は行を R, 列を C, 番号を # で表記すれば、(1,1,1) から (9,9,9) まで

R₁C₁#1, R₁C₁#2, …, R₉C₉#9

の形に書けます。

数独の制約は以下の 4 つです。

各マス i, j に注目すると、1から9までの数字のどれか一つしか入らない
R_iC_j = { R_iC_j#1, R_iC_j#2, R_iC_j#3, ..., R_iC_j#9 }.　(1 ≤ i, j ≤ 9)
各行 i と数字 n に注目すると、数字 n は列 1 から列 9 までのどれか一つしか入らない
R_i#n = { R_iC₁#n, R_iC₂#n, R_iC₃#n, ..., R_iC₉#n }. (1 ≤ i, n ≤ 9)
各列 j と数字 n に注目すると、数字 n は行 1 から行 9 までのどれか一つしか入らない
C_j#n = { R₁C_j#n, R₂C_j#n, R₃C_j#n, ..., R₉C_j#n }. (1 ≤ j, n ≤ 9)
9個ある 3x3 ボックスと数字 n に注目すると、数字 n は各ボックスのどこかに入る（例として左上のボックス）
B₁#n = { R₁C₁#n, R₁C₂#n, R₁C₃#n, R₂C₁#n,R₂C₂#n, R₂C₃#n, R₃C₁#n,R₃C₂#n, R₃C₃#n }. (ボックスは9個; 1 ≤ n ≤ 9)

上記の 4 制約それぞれが 9x9 パターンあるので、合計で 4 * 81 = 324 制約です。それぞれの制約として、729 個の選択肢からちょうど 9 個ずつ選ばれた Exact Hitting Set 問題になっています。

制約には規則性があります。例えばマス (1,1) に 1 を入れる選択肢 R₁C₁#1 は、上記の制約のうち { R₁C₁, R₁#1, C₁#1, B₁#1} という4つの制約に現れます。同様にすべての選択肢は、正確に4回ずつ、規則性を持って出現します。ただし、数独の問題で実際に数字が埋まっている部分は、選択肢の数が9個ではなく1個に減ります。

ただし 9 x 9 の数独は、Hitting Setとして解釈しなくても全解探索ですぐに解けます（Javaプログラム）。

@@ Line 1: / Line 1: @@
+{{Lecture/Header}}
 ==KnuthのアルゴリズムX==
 Donald KnuthはTeXの開発者、"The Art of Programming"の著者で、様々なアルゴリズムも開発した著名な計算機科学者です。
@@ Line 4: / Line 6: @@
 ここではExact Cover, Hitting Setという問題の説明と、それを用いた数独の解法について解説します。
-==Exact Cover by 3-Sets==
+* Algorithm X の [[Aritalab:Lecture/Programming/Java/AlgorithmX| Javaコード]]
-Exact Coverとは、以下の組み合わせ問題です。
+* Algorithm X より速い簡単なバックトラック Sudoku solver [[Aritalab:Lecture/Programming/Java/Sudoku| Javaコード]]
-; 設定: 3の倍数ぶん要素を持つ集合Xと、要素の三つ組みの集合C
+==Exact Cover==
+以下の組み合わせ問題を　Exact Cover　と呼びます。
+; 設定: 集合Xと、Xの部分集合からなる集合C
 ; 問題: Cの部分集合 C'&sube;Cで、Xの要素が全てぴったり1回だけ現れるものがあるか？
-この問題は3DMと呼ばれる問題と等価で、NP完全であることが示されています。
+この問題は[[Aritalab:Lecture/Algorithm/Reducibility|3DMと呼ばれる問題を部分問題として含むため、NP完全である]]ことが示されています。
 ; 例
 集合 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 になっています。
+この例では、 {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 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問題と全く同じ条件を読み替えている点を理解してみましょう。
+上の場合は　{A, D} という部分集合が、Exact Hitting Set になっています。この問題、実は、Exact Cover 問題に同じです。
+Exact Cover　における集合 X の各要素について、それを含む部分集合 C のラベルを集めた集合を作っておけばよいからです。
+{| class="wikitable" style="width:200px"
+|-
+!   ||  1 || 2 || 3 || 4 || 5 || 6
+|-
+! <span style="color:red">A</span>
+| ✖ || ✖ ||  || ✖ ||  ||
+|-
+! B
+| ✖ ||  || ✖ || ✖ ||  ||
+|-
+! C
+| ✖ ||  || ✖ ||  || ✖ ||
+|-
+! <span style="color:red">D</span>
+|  ||  || ✖ ||  || ✖ || ✖
+|-
+! E
+|  || ✖ || ✖ ||  ||  || ✖
+|}
 ==Sudoku==
-一般的な数独は9x9の升目に1から9の数が入るので、9x9x9=729通りの可能性があります。
+ここで、数独が Hitting Set の部分問題であることを示しましょう。
-全てのパターンは行をR, 列をC, 番号を#で表記すれば、(1,1,1)から(9,9,9)まで
+一般的な数独は 9 x 9 のマス目に 1 から 9 の数が入るので、9x9x9 = 729 個の選択肢があります。つまり、集合 S の要素が729個です。
+これらの要素は行を 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までの数字のどれか一つしか入らない<br/>
+<ol>
+<li> 各マス '''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 &le; i, j &le; 9)
-* 全ての行iと数字nにおいて、
+<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において、
+<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)
-* 全ての3x3ボックスと数字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)
+</ol>
-と書けます。制約の数は、上記の4制約全てについて9x9パターンあるので4 * 81 = 324通りです。
+上記の 4 制約それぞれが 9x9 パターンあるので、合計で 4 * 81 = 324 制約です。それぞれの制約として、729 個の選択肢からちょうど 9 個ずつ選ばれた Exact 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通りの制約に現れます。729ある選択肢が制約中に出現するパターンには対称性がありますが、数独の問題で実際に数字が埋まっている部分があれば、選択肢の数が9個ではなく1個になります。
-この問題設定は上記の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個に減ります。
-数独は、Hitting Setとして解釈しなくても全解探索ですぐに解ける（[[Aritalab:Lecture/Programming/Java/Sudoku|Javaプログラム]]）のですが、理論としてはNP完全問題と同じ構造を持つということです。
+ただし 9 x 9 の数独は、Hitting Setとして解釈しなくても全解探索ですぐに解けます（[[Aritalab:Lecture/Programming/Java/Sudoku|Javaプログラム]]）。

Aritalab:Lecture/Algorithm/Sudoku

Latest revision as of 14:55, 22 August 2017

Contents

[edit] KnuthのアルゴリズムX

[edit] Exact Cover

[edit] Hitting Set

[edit] Sudoku

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

metabolites

Toolbox