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.)
#!/usr/bin/perl -w
use strict;
my $sudoku = ("^.*" .
(join ".*\n.*", "(.)",
map {
my $n = $_;
("(?!" .
(join "|",
(map "\\" . ($_+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))) .
")(.)");
} 1..80) .
".*\$"
);
while (<>) {
chomp;
length != 81 || tr/1-9_//c and (print("Bad input.\n"), next);
s/(.)/$1 eq "_" ? "123456789\n" : "$1\n"/eg;
print((join("", /$sudoku/) || "No solution."), "\n");
}
__END__
Input, in case it's not obvious from the code, is an 81-character string
listing the numbers in left-right, top-down order, with "_" for blanks.
The while loop mangles it into the proper format for the regexp (81
lines, each listing the allowed numbers for the corresponding cell) and
outputs the solution in the same format as the input.
--
Ilmari Karonen
