Re: /$sudoku/

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