3行数独ソルバー

Perlで書かれた三行の数独ソルバーと、その解説。


なるほど、完全に探索だけで解決している。

以下、ソースの解読:

@A = split //, <>;

入力は81文字の数字。インデックスと数独上の位置関係は、フラットに横に並べたものとして扱っている。0は空のセル。それをひとつづつ分けて配列@Aに入れている。

sub R {
    for $i ( 0 .. 80 ) {

ソルバー関数Rはセルをすべてなぞる。

        next if $A[$i];

セルが0でない場合はパス。

        my %t = map {
                 $_ / 9 == $i / 9
              || $_ % 9 == $i % 9
              || $_ / 27 == $i / 27 && $_ % 9 / 3 == $i % 9 / 3
              ? $A[$_]
              : 0 => 1
        } 0 .. 80;

この$i番目のセルと同じ、横列($i / 9)、縦列($i % 9)、小ブロック($i / 27 かつ $i % 9 / 3)にあるセルに入っている値を、すべて集めたセットが%t。

        R( $A[$i] = $_ ) for grep { !$t{$_} } 1 .. 9;

%tに入ってない値を順に(初期値に0が入っていた)セルにセットし、再帰的に探索。
この文は、 for my $v (grep {!$t{$_}} (1..9)) { $A[$i] = $v; R(); } と同じ。

        return $A[$i] = 0;

失敗したのでそのセルを0にクリアして、リターン。重要なのは$A[$i]を元にもどしてから、このセルの処理を終えること。このセルで解となる可能性がないことが判明したので、$iをこれ以上進めず、ひとつセルを戻して次の候補を選ばせることになる。この文は、処理を1文で済ますためにリターンで代入しており、このリターン値は計算には関係なし。

    }
    die @A;

ループが終わったときは、すべてのセルが0でない、つまり答えが見つかったとき。
dieによって、結果を表示し、終了する(結果のあとにエラー文も出力されるけど)。

}
R

ソルバーを実行。


ほぼ8クイーンと同じバックトラックを使ったやり方、つまりひとつづつ、セットしてみて、進めていき、失敗したら戻る、というもの。
表示にdieではなく、printにすれば、全パターンを表示させられる(重複は出ない)。