Aritalab:Lecture/Algorithm/Sudoku

Revision as of 01:10, 13 October 2011

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

以下の組み合わせ問題を　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 です。 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};

Sudoku

ここで、数独が Exact Cover 問題に等しいことを示しましょう。 一般的な数独は9x9の升目に1から9の数が入るので、9x9x9=729個の選択肢を持ちます。つまり、集合 S の要素が729個です。 これらの要素は行をR, 列をC, 番号を#で表記すれば、(1,1,1)から(9,9,9)まで

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

の形に書けます。

数独の制約は

各マス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つに分けられます。制約の数は、上記の4制約それぞれについて9x9パターンあるので4 * 81 = 324通りです。 つまり Exact Hitting Set 問題の例で 1～6 とあった制約が324個に増え、それぞれの制約にはちょうと9通りの選択肢があるのです。 この問題設定は上記のHitting Setと同じですね。

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

数独は、Hitting Setとして解釈しなくても全解探索ですぐに解ける（Javaプログラム）のですが、理論的にはNP完全問題と同じ構造を持つということです。