DLX：コンピュータを使ってパズルを解く：SSブログ

	ブログをはじめるログイン

数独を解く　 [DLX]

ここで使っているパズル解きのプログラムは、Knuth先生のAlgorithm XをDancing Linksで実装したもの(DLXと呼びます)です。
Algorithm XやDancing Linksの詳細は、ググればわかりやすい解説のページがでてきますので、割愛します。
また、数独をDLXで解く方法については、数独を「Exact Conver」問題として適用するのですが、これも割愛します。

Knuth先生の書かれたプログラムを実際に動かしてみましょう。

Knuth先生の書かれたプログラムは、以下のページにあります。
http://www-cs-faculty.stanford.edu/~uno/programs.html
この中から「DANCE」と「SUDOKU」のリンクでdance.w, sudoku.wをダウンロードします。

この.wの拡張子ですが、これはCWEBというものらしく、プログラムとドキュメントが一体化したものです。
ですので、コンパイルするには、ソースを取り出すプログラム(ctangle)が必要です。
ctangleは、livetexなどのパッケージに含まれているようです。他に、Knuth先生の次のページからソースをダウンロードできます。
http://www-cs-faculty.stanford.edu/~uno/cweb.html

通常のlinuxの環境では、次のコマンドでdance,sudokuのプログラムがビルドできます。

   ctangle dance.w
   make dance
   ctangle sudoku.w
   make sudoku

なお、ドキュメントは、PDFで見る場合は、

   cweave dance.w
   tex dance
   dvipdf dance.dvi

のようになります。

さて、これをどう使うのでしょう?
数独の問題は、9x9のマスで構成されていますので、問題は、たとえば次のようになります。
これは、中央の9マスの数字を求める問題です。空欄は'.'として、9文字の9行で入力します。

これを次のコマンドラインに入力します。ファイルに書いておいて、リダイレクトするとよいでしょう。
ファイル名をprobremとしますと

./sudoku <probrem | ./dance 1

結果は次のように表示されます。

1:
 p33 r35 c35 b45 (1 of 1)
 p34 r36 c46 b46 (1 of 1)
 p35 r37 c57 b47 (1 of 1)
 p43 r48 c38 b48 (1 of 1)
 p44 r49 c49 b49 (1 of 1)
 p45 r41 c51 b41 (1 of 1)
 p53 r52 c32 b42 (1 of 1)
 p54 r53 c43 b43 (1 of 1)
 p55 r54 c54 b44 (1 of 1)
Altogether 1 solutions, after 63 updates.
     0     1     1 nodes, 7 updates
     0     1     1 nodes, 7 updates
     0     1     1 nodes, 7 updates
     0     1     1 nodes, 7 updates
     0     1     1 nodes, 7 updates
     0     1     1 nodes, 7 updates
     0     1     1 nodes, 7 updates
     0     1     1 nodes, 7 updates
     1     0     1 nodes, 7 updates
Total 10 nodes.

これではよく分からないですね。では、上記の結果を表示するプログラムをつくりましょう。

display_sudoku_dance_answer.plとします。以下のようなものです。

#!/usr/bin/perl
use strict;
my $inAns=0;
my @board=();
while(<>) {
    my $lin=$_;
    chomp $lin;
    if ($inAns) {
        if ($lin=~m{\s+([a-z]\d\d)\s+([a-z]\d\d)\s+([a-z]\d\d)\s+([a-z]\d\d)\s+}) {
            # p13 r11 c31 b11 (1 of 1)
            # r65 c05 b65 p60 (1 of 1)
            my @col=($1,$2,$3,$4);
            # find pXY
            my ($x,$y)=(undef,undef);
            my $dgt=undef;
            for my $col (@col) {
                if ($col=~m{p(\d)(\d)}) {
                    ($y,$x)=($1,$2);   # fixed bug
                    if (defined($dgt)) { last; }
                    next;
                }
                elsif ($col=~m{[a-z]\d(\d)}) {
                    $dgt=$1;
                    if (defined($x)) { last; }
                    next;
                }
            }
            if (!defined($x)||!defined($dgt)) {
                # error
                print "ERROR: internal error.\n";
                exit 1;
            }
            $board[$y][$x]=$dgt;
            next;
        }
        else {
            # disp answer
            for (my $y=0; $y<9; $y++) {
                for (my $x=0; $x<9; $x++) {
                    if (!defined($board[$y][$x])) {
                        print ".";
                    }
                    else {
                        print $board[$y][$x];
                    }
                    if ($x<8 && $x%3==2) {
                        print "|";
                    }
                }
                print "\n";
                if ($y<8 && $y%3==2) {
                    print "---+---+---\n";
                }
            }
            $inAns=0;
            # thru to check ans number
        }
    }
    if ($lin=~m{^\s*(\d+)\s*:}) {
        # ans number
        print "$lin\n";
        $inAns=1;
        next;
    }
}

実行してみましょう。

./sudoku <probrem | ./dance 1 | ./display_sudoku_dance_answer.pl

結果は、次のようになります。

1:
...|...|...
...|...|...
...|...|...
---+---+---
...|567|...
...|891|...
...|234|...
---+---+---
...|...|...
...|...|...
...|...|...

では、少し考察してみましょう。

danceが出力した解の後ろに、どれだけ(大雑把に言うと)「手順」がかかったかが表示されています。

Altogether 1 solutions, after 63 updates.

このprogremでは63回の「手順」で全解(1個)が求まっています。
人が解いても簡単な問題ですね。

では、「世界一難しい」と銘打たれた数独の問題がどれだけ難しいかを、「手順」の数でみてみましょう。

「世界一難しい数独」でググると、2つの問題がヒットします。
ひとつは2010年のもの、もうひとつは2012年のものです。

それを入力してみると、「手順」は、

2010年の問題
Altogether 1 solutions, after 10676 updates.

2012年の問題
Altogether 1 solutions, after 50570 updates.

となりました。手順で5倍も大きいものとなっていますので、人が考える場合は5倍よりもかなり難しくなっているでしょう。
数独の難しさも「進化」していますね(^^)。

なお、DLXでの「手順」の数は、実は、同じ問題でも、問題の数値を入力する順序によってある程度変わってきます(変わらないこともあります)。
これは、dance.cでのbest_colの選択方法(同一のbest値があった場合の選択方法)によるためですが、興味ある方はAlgorithm Xの解説を調べてください。