Re: /$sudoku/

Nyttigt regexp :-)

On Thursday 20 April 2006 16:03, 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.)
>
> #!/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.