The game of sudoku is basically a 9x9 grid made out of 9 3x3 grids. The rule is quite simple: given the known numbers in the grid, fill in the rest of the numbers between 1 and 9, so that each number only appear once horizontally, virtically and within each of the 3x3 block...
To run the sudoku solver below, start the program, cut and paste the puzzles, the answer will be printed automatically.
$_=q`I=0;while(<>){chomp;next()if((/^\s*#/)or(!$_));_z()unless@o;my@p=
+/(\S)/g;for(J=0;$j<9;$j++){_y($i,$j,$p[$j])if($p[$
j]=~/\d/)}if(++$i>8){$i=0;$p=0;while(!_w()){if($p==$c){$p=0;_q()}$p=$c
+}_x();undef(@o)}}Zfor(I=0;$i<9;$i++){for(J=0;$j<9;
$j + + ) { $
+ o [ $ i]
[$ j ]= ' 1 2345 6 7
+ 8 9'}}$c = 0 }Ymy($ i,
$j , $e)= @ _ ;$ o[ $ i
+ ] [$ j ] =$ e;
$c + +; fo r ( F= 0 ;
+ $ f< 9 ; $f ++
){ n ex t( ) i f( $ f
+ = =$ j ) or ($o[ $i
][ $ f]<10);$o[ $ i ][ $ f
+ ] =~ s / $e// ;i f(
$o [ $i ] [ $f ] <
+ 1 0) { _ y( $i ,$
f, $ o[ $ i ][$f])}}fo r (
+ F =0;$f<9; $ f ++){ne xt
() i f ( $ f
+ = = $ i)
or($o[$f][$j]<10);$o[$f][$j]=~s/$e//;if($o[$f][$j]<10){_y($f,$j,$o[$f]
+[$j])}}A=int($i/3)*3;B=int($j/3)*3;for(F=$a;$f<$a+
3; $ f + + )
+ { f o r(
D= $ b ; $ d
+<$b+3; $ d++){next( ) i f(
($ f = = $ i )a
+ nd ( $d = = $j
)) o r ( $ o [$
+ f] [ $d ] < 10
); $ o [ $ f
+][$d]= ~ s/ $ e //
;i f ( $ o [ $f
+ ][ $ d] < 1 0)
{_ y ( $ f , $d
+ ,$ o [$ f ] [$
d] ) } } } }
+Wretur n (1 ) i f(
$c = = 8 1 )
+ ; f o r(
I=0;$i<9;$i++){for(J=0;$j<9;$j++){next()if($o[$i][$j]<10);forE(split(/
+/,$o[$i][$j])){if((_v($i,$j,$e))or(_u($i,$j,$e))or
(_ t ( $ i ,
+ $ j , $e
)) ) { _ y($i,$ j , $e
+);re t u r n(
1) i f ( $c = =
+ 81 ) ; l as
t} } } } fo r (
+ A= 0 ; $ a<
3; $ a + +) { f
+or(B = 0 ; $b
<3 ; $ b ++ ) {
+ fo r ( E =1
;$ e < 1 0; $ e
+ ++ ) { m y@
p= _ s ( $a*3,$b* 3 , $e
+);my @ n = _r
($ a * 3 , $
+ b * 3 ,$
e);if((@p==1)and(@n>1)){for(I=0;$i<9;$i++){next()if(($i>=$a*3)and($i<$
+a*3+3))or($o[$i][$p[0]]<10);$o[$i][$p[0]]=~s/$e//;
if ( $ o [ $
+ i ] [ $p
[0 ]]<10) { _y($ i , $ p [0
+],$o[$i] [ $ p [0
]] ); r et ur n ( 1 )
+ if ( $ c ==
81 )} } }i f ( ( @
+ n= = 1 ) an
d( @p > 1) ) { f o
+ r( J = 0 ;$
j< 9; $ j+ + ) { n
+ex t ( ) if
(( $j > =$ b * 3 )
+an d ( $ j<
$b *3+3))or($ o [$n[0]][$j ] < 1 0 );
+ $ o [ $n
[0 ] ] [ $ j
+ ] = ~ s/
$e//;if($o[$n[0]][$j]<10){_y($n[0],$j,$o[$n[0]][$j]);return(1)if($c==8
+1)}}}}}}for(A=0;$a<3;$a++){for(B=0;$b<3;$b++){for(
E= 1 ; $ e <
+ 1 0 ; $e
++ ) { my @ p =
+ _ s($a*3 , $ b*
3, $ e );my @ n =
+ _ r( $ a *3
,$ b * 3, $e ) ; i
+ f (( @ p ==
1) a n d( @n = = 2
+ ) ){ for( G = 0;
$g < 3 ;$g++){nex t ( )
+ i f($b == $ g );
my @ m =_ s ( $
+ a *3 ,$ g * 3,
$e ) ; my @ l =
+ _ r($a*3 , $ g*
3, $ e ) ; i
+ f ( ( @m
==1)and(join('',@n)==join('',@l))){forI(@n){H=3-$b-$g;for(J=$h*3;$j<$h
+*3+3;$j++){next()if($o[$i][$j]<10);$o[$i][$j]=~s/$
e/ / ; i f (
+ $ o [ $i
][ $ j ] <1 0 )
+ { _ y($i,$j,$o [ $i][$j ])
;r e t u rn(1 ) i
+ f ( $c = =8 1) }}
}} } } e ls if ( (
+ @ n == 1 )a nd (@
p= = 2 ) ){ fo r (
+ G = 0; $ g<3;$g++ ){
ne x t ( )if($a==$g ) ;
+ m y @m = _s ($
g* 3 , $ b* 3 ,
+ $ e ); m y@ l=
_r ( $ g *3 , $
+ b * 3, $ e);if( (@
l= = 1 ) a n
+ d ( j oi
n('',@p)==join('',@m))){forJ(@p){H=3-$a-$g;for(I=$h*3;$i<$h*3+3;$i++){
+next()if($o[$i][$j]<10);$o[$i][$j]=~s/$e//;if($o[$
i] [ $ j ] <
+ 1 0 ) {_
y( $ i , $j,$o[ $ i ][
+$j]) ; r e tu
rn ( 1 ) if ( $
+ c= = 8 1 )}
}} } } } }} } r
+ et u r n ($
c= = 8 1 )} V m
+y($i , $ j ,$
e) = @ _ ;f o r
+ (F = 0 ; $f
<9 ; $ f ++ ) {
+ ne x t ( )i
f( $ f = =$j);ret u r n(
+0)if ( $ o [$
i] [ $ f ] =
+ ~ / $ e/
)}return(1)}Umy($i,$j,$e)=@_;for(F=0;$f<9;$f++){next()if($f==$i);retur
+n(0)if($o[$f][$j]=~/$e/)}return(1)}Tmy($i,$j,$e)=@
_; A = i n t
+ ( $ i /3
)* 3 ; B=int($j / 3)*3;f o r
+ ( F = $a
;$ f < $a + 3; $f + +
+ ) { f or
(D = $ b; $ d< $b + 3
+ ; $ d ++
){ n e xt()if ( $f==$i)a n d
+ ( $ d ==
$j ) ; re t ur n (
+ 0 ) i f(
$o [ $ f] [ $d ] =
+ ~ / $ e/
)} } r eturn( 1 )}Smy( $ i
+ , $ j ,$
e) = @ _ ; A
+ = i n t(
$i/3)*3;B=int($j/3)*3;my%k;for(F=$a;$f<$a+3;$f++){for(D=$b;$d<$b+3;$d+
++){$k{$d}++if($o[$f][$d]=~/$e/)}}return(sort(keys(
%k ) ) ) } R
+ m y ( $i
,$ j,$e ) = @_;A=i n t (
+ $i/3)* 3 ; B=int($j / 3)
*3 ;m y% k ; fo r( F = $
+a; $ f <$ a +3
;$ f+ + ) {f or ( D = $b
+ ; $ d< $ b+
3; $d + + ){$k{$f} + + i f(
+ $o[$ f ] [$d]=~ / $e
/) ;} ; } re t u r n(
+so rt ( k ey s (%
k) )) } Q sr a n d (t
+ im e ) ;w h il
e( ){F=int(ra n d (9));D = i n
+t(rand ( 9 ));nex t ()
if ( $ o [ $
+ f ] [ $d
]<10);E=$o[$f][$d];$e=substr($e,int(rand(length($e))),1);_y($f,$d,$e);
+last};}Xfor(my $i=0;$i<9;$i++){print(join(chr(32),
@{$o[$i]}),"\n");;}print("\n");};`;s/\s//gx;s/(?<!\\)([Q-Z])/sub _\l$1
+\{/gx;s/([A-J])/my \$\l$1/gx;s/formy/for my/g;eval
Puzzles in the form of:
# Puzzle #1
* 8 * * * * * 4 *
* 3 * * * 8 * * *
* * 1 * * 2 * 6 3
* * 2 8 4 7 * * 6
* * * * * * * * *
7 * * 2 9 3 5 * *
1 2 * 5 * * 7 * *
* * * 3 * * * 1 *
* 9 * * * * * 5 *
# Puzzle #2
* * * * 1 8 5 * 9
* * 5 4 * * * * *
* * 4 * 6 9 * 2 7
7 4 * * * * * * *
* 1 * * * * * 5 *
* * * * * * * 8 6
5 7 * 6 8 * 4 * *
* * * * * 7 6 * *
8 * 3 1 9 * * * *
# Puzzle #3
* * * 9 * * * * *
* 9 * 2 * * 8 * *
3 8 * * * * 7 * 9
* * * * 4 1 2 * *
9 * * * * * * * 7
* * 4 6 3 * * * *
7 * 2 * * * * 4 5
* * 5 * * 7 * 3 *
* * * * * 4 * 7 *
