Abbadon
New User
Feb 20, 2007, 10:15 PM
Post #1 of 2
(1436 views)
|
|
Scope issues with recursion in sudoku solver
|
Can't Post
|
|
Hi, for some reason the value of a variable in a higher nesting level isn't being restored and thus my recursive subroutine terminates in failure. If anybody could have a look at it and figure out what's wrong, that would be appreciated.
#!/usr/bin/perl
open(FILE, "sudoku.txt");
@lines = <FILE>;
close(FILE);
chomp(@lines);
@line0 = split(//,$lines[0]);
@line1 = split(//,$lines[1]);
@line2 = split(//,$lines[2]);
@line3 = split(//,$lines[3]);
@line4 = split(//,$lines[4]);
@line5 = split(//,$lines[5]);
@line6 = split(//,$lines[6]);
@line7 = split(//,$lines[7]);
@line8 = split(//,$lines[8]);
@puzzle = ( \@line0, \@line1, \@line2, \@line3, \@line4, \@line5, \@line6,
\@line7, \@line8 );
@ln0 = ("n","n","n","n","n","n","n","n","n");
@ln1 = ("n","n","n","n","n","n","n","n","n");
@ln2 = ("n","n","n","n","n","n","n","n","n");
@ln3 = ("n","n","n","n","n","n","n","n","n");
@ln4 = ("n","n","n","n","n","n","n","n","n");
@ln5 = ("n","n","n","n","n","n","n","n","n");
@ln6 = ("n","n","n","n","n","n","n","n","n");
@ln7 = ("n","n","n","n","n","n","n","n","n");
@ln8 = ("n","n","n","n","n","n","n","n","n");
@ps = ( \@ln0, \@ln1, \@ln2, \@ln3, \@ln4, \@ln5, \@ln6, \@ln7, \@ln8 );
for($i = 0; $i < 9; $i++){
for($j = 0; $j < 9; $j++){
if( $puzzle[$i][$j] =~ m/n/ ){
$ps[$i][$j] = "123456789";
}else{
$ps[$i][$j] = $puzzle[$i][$j];
}
}
}
sub mark{
$y = $_[0];
#print $y;
$x = $_[1];
#print $x;
$tomark = $_[2];
#print $tomark;
my @pos;
my @psb = $_[3];
for($i = 0; $i < 9; $i++){
for($j = 0; $j < 9; $j++){
$pos[$i][$j] = $psb[0][$i][$j];
}
}
for($i = 0; $i < 9; $i++){
if($i != $y){
$pos[$i][$x] =~ s/[$tomark]//g;
}
if($i != $x){
$pos[$y][$i] =~ s/[$tomark]//g;
}
}
$i = 0;
$j = 0;
$boxx = ($x - ($x % 3)) / 3;
$boxy = ($y - ($y % 3)) / 3;
for($i = ($boxy * 3); $i < (($boxy * 3) + 3); $i++){
for($j = ($boxx * 3); $j < (($boxx * 3) + 3); $j++){
if(($i != $y) && ($j != $x)){
$pos[$i][$j] =~ s/[$tomark]//g;
}
}
}
return @pos;
}
sub check {
for($a = 0; $a < 9; $a++){
for($b = 0; $b < 9; $b++){
if(length($pos[$a][$b]) == 0){
return "";
}
}
}
return "1";
}
for($a = 0; $a < 9; $a++){
for($b = 0; $b < 9; $b++){
if($puzzle[$a][$b] !~ m/n/){
@ps = mark($a, $b, $puzzle[$a][$b], \@ps);
}
}
}
sub is_solved{
for($a = 0; $a < 9; $a++){
for($b = 0; $b < 9; $b++){
if(length($pos[$a][$b]) > 1){
print "multiple value found";
return "";
}
}
}
return "1";
}
sub slve {
@psb = $_[0];
$pos;
for($i = 0; $i < 9; $i++){
for($j = 0; $j < 9; $j++){
$pos[$i][$j] = $psb[0][$i][$j];
}
}
print "Solve Started\n";
if(is_solved){
print "is_solved";
return @pos;
}
for($e=0; $e < 9; $e++){
for($f=0; $f < 9; $f++){
if(length($pos[$e][$f]) == 1){
print "Preset Value\n";
next;
}
print "Deciding for $e $f \n";
for($i = 0; $i < length($pos[$e][$f]); $i++){
$pos[$e][$f] = substr($pos[$e][$f],$i, 1);
@pos = mark($e, $f, $pos[$e][$f], \@pos);
print "Try $pos[$e][$f]\n";
if($e >= 1){
for($a = 0; $a < 9; $a++){
for($b = 0; $b < 9; $b++){
print "$pos[$a][$b] ";
}
print "\n";
}
}
if(!check){
print "Failed ($e $f)\n";
next;
}
print "$pos[$e][$f] works\n";
@result = slve(\@pos);
if(!(@result)){
print "failed square\n";
next;
}
return @result;
}
print "failed square $e $f\n";
undef(@failure);
return @failure;
}
}
}
for($a = 0; $a < 9; $a++){
for($b = 0; $b < 9; $b++){
print "$ps[$a][$b] ";
}
print "\n";
}
@final = slve(\@ps);
print "\n\n";
for($a = 0; $a < 9; $a++){
for($b = 0; $b < 9; $b++){
print "$ps[$a][$b] ";
}
print "\n";
}
for($a = 0; $a < 9; $a++){
for($b = 0; $b < 9; $b++){
print $final[$a][$b];
}
print "\n";
}
This code reads:
n6n1n4n5n
nn83n56nn
2nnnnnnn1
8nn4n7nn6
nn6nnn3nn
7nn9n1nn4
5nnnnnnn2
nn72n69nn
n4n5n8n7n
in sudoku.txt.
Any help would be much appreciated, I'm sure its just something small.
|
MAIN
SEARCH
WHO'S 
LOG 
