davido brought up the subject of Sudoku puzzles (info, info) in the ChatterBox. He asked: "I've never used the RE engine for puzzles. anyone have any idea how such would be implemented?" The solution below solves Sudoku puzzles using the RE.
#!/usr/bin/perl use strict; use warnings; my @grid = ( [qw( _ _ _ | 1 _ _ | 7 4 _ )], [qw( _ 5 _ | _ 9 _ | _ 3 2 )], [qw( _ _ 6 | 7 _ _ | 9 _ _ )], # ------+-------+------- [qw( 4 _ _ | 8 _ _ | _ _ _ )], [qw( _ 2 _ | _ _ _ | _ 1 _ )], [qw( _ _ _ | _ _ 9 | _ _ 5 )], # ------+-------+------- [qw( _ _ 4 | _ _ 7 | 3 _ _ )], [qw( 7 3 _ | _ 2 _ | _ 6 _ )], [qw( _ 6 5 | _ _ 4 | _ _ _ )], ); @$_ = grep { /[^|]/ } @$_ foreach @grid; my $size = @grid; our $grid_h = ''; our $grid_v = ''; foreach my $y (0 .. $#grid) { foreach my $x (0 .. $#grid) { $grid_h .= $grid[$y][$x]; $grid_v .= $grid[$x][$y]; } } our $match_grid; sub print_grid { local $_ = $_[0]; local $\ = "\n"; print substr($_, 0, $size, '') while length; } sub valid { my $spot = substr($grid_h, $_[0]*$size+$_[1], 1); return 1 if $spot eq $_[2]; return if $spot ne '_'; return if index(substr($grid_h, $_[0] * $size, $size), $_[2]) >= 0; return if index(substr($grid_v, $_[1] * $size, $size), $_[2]) >= 0; return 1; } my $re = ''; my $fail = 'x'; foreach my $y (0 .. $#grid) { foreach my $x (0 .. $#grid) { my @attempts; foreach my $n (1 .. @grid) { # The following statment simplifies the regexp, # but makes it specific to the puzzle. # Comment it out to make the regexp reusable. next unless valid($y, $x, "$n"); push(@attempts, "(?(?{ !valid($y, $x, '$n') })$fail)" . "(?{ " . "local \$grid_h = \$grid_h; " . "substr(\$grid_h, @{[ $y*$size+$x ]}, 1, '$n'); " . "local \$grid_v = \$grid_v; " . "substr(\$grid_v, @{[ $x*$size+$y ]}, 1, '$n'); " . "})" ); } $re .= "(?:\n " . join(" |\n ", @attempts) . "\n)\n"; } } $re .= "(?{ \$match_grid = \$grid_h })\n"; { use re 'eval'; $re = qr/$re/x; } # print($re); "" =~ $re or die("No solution.\n"); print("Original\n"); print("========\n"); print_grid($grid_h); print("\n"); print("Solution\n"); print("========\n"); print_grid($match_grid);
Original ======== ___1__74_ _5__9__32 __67__9__ 4__8_____ _2_____1_ _____9__5 __4__73__ 73__2__6_ _65__4___ Solution ======== 283156749 157498632 316742958 471835296 529683417 642319875 894567321 738921564 965274183
Comment: This solution localizes the entire grid twice for every attempt, so it uses a lot of memory. It does this to speed up valid. I'm not sure if the cost is worth the benefit. The alternative would be to keep the grid as an array, and just localize the array element.
Comment: This program supports grids of any size (well, 4x4, 9x9, 16x16, ...), although minor tweaking will be needed to generate single character values other than 0-9 for sizes greater than 9x9.
This post is related to this one.
|
---|
Replies are listed 'Best First'. | |
---|---|
Re: Sudoku puzzles solved using Regular Expressions
by davido (Cardinal) on Jun 30, 2005 at 01:07 UTC | |
by saskaqueer (Friar) on Jul 13, 2005 at 22:35 UTC | |
Re: Sudoku puzzles solved using Regular Expressions
by GrandFather (Saint) on Jun 30, 2005 at 00:59 UTC | |
by ikegami (Patriarch) on Jun 30, 2005 at 04:11 UTC | |
by GrandFather (Saint) on Jun 30, 2005 at 05:36 UTC | |
by ikegami (Patriarch) on Jun 30, 2005 at 05:42 UTC | |
Re: Sudoku puzzles solved using Regular Expressions
by Anonymous Monk on Jun 28, 2010 at 09:30 UTC |
Back to
Cool Uses for Perl