Aritalab:Lecture/Algorithm/Sudoku

Wiki Top

Up one level

レポートの書き方

Arita Laboratory

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コード

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 はありません。

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		✖	✖			✖

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 つです。

1. 各マス 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)

2. 各行 i と数字 n に注目すると、数字 n は列 1 から列 9 までのどれか一つしか入らない

   R_i#n = { R_iC₁#n, R_iC₂#n, R_iC₃#n, ..., R_iC₉#n }. (1 ≤ i, n ≤ 9)

3. 各列 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)

4. 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プログラム）。