Home: Perl Programming Help: Intermediate:
Scope issues with recursion in sudoku solver



Abbadon
New User

Feb 20, 2007, 10:15 PM


Views: 4200
Scope issues with recursion in sudoku solver

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.


KevinR
Veteran


Feb 20, 2007, 10:47 PM


Views: 4199
Re: [Abbadon] Scope issues with recursion in sudoku solver

I don't mean or want to sound like I'm being disrespectful or condescending twards you, but nobody here is going to wade through all that unformatted code to try and find your error(s) in syntax or logic.

Start again, using "strict" and "warnings". Don't use $a and $b as they are special perl variables, but I doubt they are causing your problem, whatever the problem is.
-------------------------------------------------