Ilmari Karonen wrote:
Sudoku solvers are old hat, of course, but this one is a bit different:
it's a regexp. I suppose someone may have done this before, but if so,
I haven't seen it. It's grossly inefficient, of course, solving the
puzzle entirely by guesswork and backtracking, but that's not really the
point. (It could be made quite a bit faster by hardcoding the givens in
the regexp, but that would make the regexp non-generic.)
Incidentally, here's the hardcoded-givens version. It's indeed quite a
lot faster the generic version -- I've yet to find a puzzle that would
take more than 0.1 seconds to solve on my workstation.
#!/usr/bin/perl -w
use strict;
while (defined(my $str = <>)) {
chomp $str;
length($str) != 81 || $str =~ tr/1-9_//c
and (print("Bad input.\n"), next);
$str =~ tr/_/0/;
my $sudoku = ("^.*" .
(join ".*\n.*",
map {
my $n = $_;
("(?!" .
((join "|",
(map substr($str,$_,1) ||
($_ < $n ? "\\" . ($_+1) : ()),
(grep $_ != $n &&
(int($_ % 9) == int($n % 9) ||
int($_ / 9) == int($n / 9) ||
int($_ / 27) == int($n / 27) &&
int($_ / 3 % 3) == int($n / 3 % 3)),
0..80))) || "x") .
")(.)");
} 0..80) .
".*\$"
);
$str =~ s/(.)/$1 ? "$1\n" : "123456789\n"/eg;
print((join("", $str =~ /$sudoku/) || "No solution."), "\n");
}
__END__
--
Ilmari Karonen
