Aritalab:Lecture/Algorithm/Sudoku
From Metabolomics.JP
< Aritalab:Lecture | Algorithm(Difference between revisions)
m (→Exact Cover by 3-Sets) |
m |
||
| (5 intermediate revisions by one user not shown) | |||
| Line 6: | Line 6: | ||
ここではExact Cover, Hitting Setという問題の説明と、それを用いた数独の解法について解説します。 | ここではExact Cover, Hitting Setという問題の説明と、それを用いた数独の解法について解説します。 | ||
| − | ==Exact Cover | + | * Algorithm X の [[Aritalab:Lecture/Programming/Java/AlgorithmX| Javaコード]] |
| + | * Algorithm X より速い簡単なバックトラック Sudoku solver [[Aritalab:Lecture/Programming/Java/Sudoku| Javaコード]] | ||
| + | |||
| + | ==Exact Cover== | ||
以下の組み合わせ問題を Exact Cover と呼びます。 | 以下の組み合わせ問題を Exact Cover と呼びます。 | ||
| − | ; 設定: | + | ; 設定: 集合Xと、Xの部分集合からなる集合C |
; 問題: Cの部分集合 C'⊆Cで、Xの要素が全てぴったり1回だけ現れるものがあるか？ | ; 問題: Cの部分集合 C'⊆Cで、Xの要素が全てぴったり1回だけ現れるものがあるか？ | ||
| − | この問題は[[Aritalab:Lecture/Algorithm/Reducibility| | + | この問題は[[Aritalab:Lecture/Algorithm/Reducibility|3DMと呼ばれる問題を部分問題として含むため、NP完全である]]ことが示されています。 |
; 例 | ; 例 | ||
| Line 31: | Line 34: | ||
; 問題: Sの部分集合S', |S'| ≤ K で、Cのどの部分集合とも少なくとも一つ重なる要素を持つものがあるか？ | ; 問題: Sの部分集合S', |S'| ≤ K で、Cのどの部分集合とも少なくとも一つ重なる要素を持つものがあるか？ | ||
| − | この条件をきつくして、ちょうど一回だけ重なる要素を持つ、としたものが Exact Hitting Set | + | この条件をきつくして、ちょうど一回だけ重なる要素を持つ、としたものが Exact Hitting Set と呼ばれる問題です。 |
| − | + | ||
| − | + | ||
; 例 | ; 例 | ||
| Line 44: | Line 45: | ||
* 6 = {<span style="color:red">D</span>, E}; | * 6 = {<span style="color:red">D</span>, E}; | ||
| + | 上の場合は {A, D} という部分集合が、Exact Hitting Set になっています。この問題、実は、Exact Cover 問題に同じです。 | ||
| + | Exact Cover における集合 X の各要素について、それを含む部分集合 C のラベルを集めた集合を作っておけばよいからです。 | ||
| − | + | {| class="wikitable" style="width:200px" | |
| − | {| | + | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
|- | |- | ||
! || 1 || 2 || 3 || 4 || 5 || 6 | ! || 1 || 2 || 3 || 4 || 5 || 6 | ||
|- | |- | ||
! <span style="color:red">A</span> | ! <span style="color:red">A</span> | ||
| − | | | + | | ✖ || ✖ || || ✖ || || |
|- | |- | ||
! B | ! B | ||
| − | | | + | | ✖ || || ✖ || ✖ || || |
|- | |- | ||
! C | ! C | ||
| − | | | + | | ✖ || || ✖ || || ✖ || |
|- | |- | ||
! <span style="color:red">D</span> | ! <span style="color:red">D</span> | ||
| − | | || || | + | | || || ✖ || || ✖ || ✖ |
|- | |- | ||
! E | ! E | ||
| − | | || | + | | || ✖ || ✖ || || || ✖ |
| − | + | ||
|} | |} | ||
==Sudoku== | ==Sudoku== | ||
| − | ここで、数独が | + | ここで、数独が Hitting Set の部分問題であることを示しましょう。 |
| − | + | 一般的な数独は 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 | : 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 つです。 | |
| − | + | <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 ≤ 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) | ||
| − | + | <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 ≤ 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) | ||
| − | + | <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 ≤ 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) | ||
| − | + | <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 ≤ 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) | ||
| + | </ol> | ||
| − | + | 上記の 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つの制約に現れます。同様にすべての選択肢は、正確に4回ずつ、規則性を持って出現します。ただし、数独の問題で実際に数字が埋まっている部分は、選択肢の数が9個ではなく1個に減ります。 | |
| − | + | ||
| − | + | ただし 9 x 9 の数独は、Hitting Setとして解釈しなくても全解探索ですぐに解けます（[[Aritalab:Lecture/Programming/Java/Sudoku|Javaプログラム]]）。 | |
Latest revision as of 14:55, 22 August 2017
| Wiki Top | Up one level | レポートの書き方 | Arita Laboratory |
|
[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という問題の説明と、それを用いた数独の解法について解説します。
[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) まで
- R1C1#1, R1C1#2, …, R9C9#9
の形に書けます。
数独の制約は以下の 4 つです。
- 各マス 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 制約それぞれが 9x9 パターンあるので、合計で 4 * 81 = 324 制約です。それぞれの制約として、729 個の選択肢からちょうど 9 個ずつ選ばれた Exact Hitting Set 問題になっています。
制約には規則性があります。例えばマス (1,1) に 1 を入れる選択肢 R1C1#1 は、上記の制約のうち { R1C1, R1#1, C1#1, B1#1} という4つの制約に現れます。同様にすべての選択肢は、正確に4回ずつ、規則性を持って出現します。ただし、数独の問題で実際に数字が埋まっている部分は、選択肢の数が9個ではなく1個に減ります。
ただし 9 x 9 の数独は、Hitting Setとして解釈しなくても全解探索ですぐに解けます（Javaプログラム）。
