CGI/Perl Guide | Learning Center | Forums | Advertise | Login
Site Search: in

  Main Index MAIN
INDEX
Search Posts SEARCH
POSTS
Who's Online WHO'S
ONLINE
Log in LOG
IN

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

 



Abbadon
New User

Feb 20, 2007, 10:15 PM

Post #1 of 2 (1766 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.


KevinR
Veteran


Feb 20, 2007, 10:47 PM

Post #2 of 2 (1765 views)
Re: [Abbadon] Scope issues with recursion in sudoku solver [In reply to] Can't Post

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.
-------------------------------------------------

 
 


Search for (options) Powered by Gossamer Forum v.1.2.0

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives