#!/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;
my $regsz = $size ** 0.5;


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 ($y, $x, $n) = @_;
   my $spot = substr($grid_h, $y*$size+$x, 1);
   return 1 if $spot eq $n;
   return   if $spot ne '_';

   return if index(substr($grid_h, $y*$size, $size), $n) >= 0;
   return if index(substr($grid_v, $x*$size, $size), $n) >= 0;

   my $ry = int($y / $regsz) * $regsz;
   my $rx = int($x / $regsz) * $regsz;
   foreach my $ry_ ($ry .. $ry+$regsz-1) {
      return if index(substr($grid_h, $ry_*$size+$rx, $regsz), $n) >= 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);