/$sudoku/

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