Re: /$sudoku/

[Ronald J Kimball]

I presented Ilmari's /$sudoku/ scripts at the Boston.pm meeting last week.
During the discussion, we thought of a further optimization.

Ilmari's first version uses a generic regular expression.  The second
version hardcodes the known values into the negative-lookahead assertions.

The optimization we came up with is to apply the known values directly in
the target string.  For example, if we know that an empty spot can't be 3,
5, or 9, then that line in the target string will be 124678.  I also made
the regex even more specific to the puzzle, although that probably doesn't
have a noticeable effect on the speed.

This version will solve puzzles in about half the time as the second
version.  However, it does move farther away from the concept of solving
the puzzle with a regex, as more work is being done outside the regex.  I
still like the purity of Ilmari's first version of the script!


Anyway, here's the code:

#!/usr/bin/perl -w

use strict;

while (defined(my $input = <>)) {
    chomp $input;
    length($input) != 81 || $input =~ tr/1-9_//c
        and (print("Bad input.\n"), next);
    $input =~ tr/_/0/;

    my $sudoku = '^';
    my $string;

    foreach my $n (0 .. 80) {
      if (my $d = substr($input, $n, 1)) {
        $string .= "$d\n";
        $sudoku .= "($d)\n";
      } else {
        $sudoku .= '.*';
        my @skip;
        my $digits = '123456789';
        foreach my $m (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) {
          if (my $e = substr($input, $m, 1)) {
            $digits =~ s/$e//;
          } elsif ($m < $n) {
            push @skip, "\\" . ($m + 1);
          }
        }
        if (@skip) {
          $sudoku .= '(?!' . join('|', @skip) . ')';
        }
        $string .= "$digits\n";
        $sudoku .= "(.).*\n";
      }
    }

    $sudoku .= '$';

    print((join("", $string =~ /$sudoku/) || "No solution."), "\n");
}

__END__


Ronald