3行数独ソルバー
なるほど、完全に探索だけで解決している。
以下、ソースの解読:
@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にすれば、全パターンを表示させられる(重複は出ない)。