#!/usr/bin/perl

# Luke Perkins

# Mass Academy

# Senior 3

# January 22, 2006

# ACSL: Sudoku Solver

# Example:

# $ cat example.txt

# 0,5,0,0,1,0,0,4,0

# 1,0,7,0,4,0,6,0,2

# 0,0,0,9,0,5,0,0,0

# 2,0,8,6,3,0,5,9,1

# 0,4,0,0,7,0,0,2,8

# 9,0,1,0,8,0,4,0,6

# 0,0,0,4,0,1,0,0,0

# 3,0,4,0,5,8,7,0,9

# 5,2,0,0,6,0,0,1,0

# 4

# 8

# 6

# 5

# 2

# $ ./sudoku.pl < example.txt

# 278634591

# 314258769

# 931582476

# 645179328

# 197843652

sub solve {

#These four variables are my'd so they don't get mixed up between recursions

my $cannot;

my $try;

my $x;

my $y;

#To show the grid as it's being solved, uncomment this:

#for($y=0;$y<9;$y++){for($x=0;$x<9;$x++){print "$grid[$y][$x]";}print "\n";}

#Go through each row

for ($y=0;$y<9;$y++) {

#Go through each column

for ($x=0;$x<9;$x++) {

# Unless this box is filled in (not 0)

unless ($grid[$y][$x])

{

# Go through each box in the same row as the current box,

# adding all the number to the list of numbers it can't be.

$cannot="";

for($x2=0;$x2<9;$x2++)

{

if($grid[$y][$x2]){$cannot.=$grid[$y][$x2]}

}

# Go through each box in the same column as the current box.

for($y2=0;$y2<9;$y2++)

{

if($grid[$y2][$x]){$cannot.=$grid[$y2][$x]}

}

# Go through each box in the same 3x3 box as the current box.

$ox=int($x/3)*3;

$oy=int($y/3)*3;

for($x2=$ox;$x2<$ox+3;$x2++)

{

for($y2=$oy;$y2<$oy+3;$y2++)

{

if($grid[$y2][$x2]){$cannot.=$grid[$y2][$x2]}

}

}

# Here it tries all the possibilities for the number at $x,$y

# It makes sure it doesn't try a number that is in the same

# column, row, or 3x3 box by first checking the $cannot list.

for $try (1 .. 9)

{

unless ($cannot=~m/$try/)

{

#Fill in the box with $try

$grid[$y][$x]=$try;

#Try solving it

solve();

}

}

#After it's done trying it can exit:

$grid[$y][$x] = 0;

# If it cannot be solved this way, return

return;

}

}

}

# At this point the grid should be complete.

# Show the five lines according to the input:

for($n=0;$n<5;$n++)

{

chomp($y=<STDIN>);

$y--;

for($x=0;$x<9;$x++)

{print "$grid[$y][$x]";}

print "\n";

}

exit;

}

# Get the incomplete grid:

for($n=0;$n<9;$n++)

{

chomp($s=<STDIN>);

$grid[$n] = [ split(/,/, $s) ];

}

solve;