#!/usr/bin/perl -w use strict; use integer; use Getopt::Std; # TODO # ---- # * Swordfish doesn't need all of the cells to have the number # * For a group with one cell of 3 possibilities and the rest of two, # mark the 3-number cell with the number that has 3 possible cells # * If $m=1 or $n=1, skip checking groups (used for latin squares) # * BUG? # # Board is $n (across) by $m (down) blocks of size $m (across) by $n (down) # each; normal boards have m=n=3. $mn=$m*$n as shorthand. my ($m,$n)=(3,3); my $mn=$m*$n; # Boards are read from stdin or as filename on the command line. # Board format is $mn lines, with space or a (hex) digit in each location. # Trailing spaces on each line are optional. # Holds solved cells in an $mn*$mn-element array. my @puzzle; # Holds possible numbers in an $mn*$mn-element array, where each element is # of the form [<#poss>,,,...,]. my @possible; # Which passes are disabled. my @skippass=(0,0,0,0,0,0,0,0,0); # Stores "amount solved" for each pass type of the algorithm. my @passfound=(0,0,0,0,0,0,0,0,0); # An array of the minimum cell index for each block. my @blockstart; # An array of the index offsets from the minimum cell index for each block. my @blockoffset; # Some command-line options (see help message for more detail). my ($showguesses,$keepguessing,$noboard,$nosolve,$showstats,$stepbystep,$useasterisk,$usebold,$verbose,$widemodein,$widemodeout,$showreasons,$digitstring,$onlyhints); sub initboard() { my ($i,$j); @puzzle=(); @possible=(); for($i=0;$i<$mn*$mn;$i++) { $puzzle[$i]=0; $possible[$i]=[$mn]; for($j=0;$j<$mn;$j++) { push @{$possible[$i]},1; } } for($i=0;$i<$mn;$i+=$n) { for($j=0;$j<$mn;$j+=$m) { push @blockstart,$mn*$i+$j; } } for($i=0;$i<$n;$i++) { for($j=0;$j<$m;$j++) { push @blockoffset,$mn*$i+$j; } } } sub sum(@) { my $total=0; $total+=shift while(@_); return $total; } sub samerow($) { my ($i)=@_; $i-=$i%$mn; return map {$i+$_} 0..$mn-1; } sub samecol($) { my ($i)=@_; $i=$i%$mn; return map {$i+$mn*$_} 0..$mn-1; } sub sameblock($) { my ($i)=@_; my $x=$i/$mn; $x-=$x%$n; # These two lines could be merged, but this way is clearer my $y=$i%$mn; $y-=$y%$m; $i=$mn*$x+$y; return map {$i+$_} @blockoffset; } sub otherrow($) { my ($i)=@_; return grep {$_ != $i} samerow($i); } sub othercol($) { my ($i)=@_; return grep {$_ != $i} samecol($i); } sub otherblock($) { my ($i)=@_; return grep {$_ != $i} sameblock($i); } sub markimpossible($$) { my ($i,$val)=@_; die "$i/$val" unless($possible[$i][$val]); die if($puzzle[$i]); $possible[$i][$val]=0; die "$i/$val" unless(--$possible[$i][0]); return 1; } sub placenum($$) { my ($i,$val)=@_; my $found=0; my ($j,$w); die "$i/$val" if($puzzle[$i]); die "$i/$val" unless($possible[$i][$val]); foreach $j (otherrow($i),othercol($i),otherblock($i)) { next unless($possible[$j][$val]); $found+=markimpossible($j,$val); } for($w=1;$w<=$mn;$w++) { next if($w==$val); next unless($possible[$i][$w]); $found+=markimpossible($i,$w); } die "$i/$val" unless(1==$possible[$i][0]); $puzzle[$i]=$val; $found++; return $found; } # Returns true if the two spots have the same set of possible numbers sub samepossible($$) { my ($a,$b)=@_; my $i; for($i=0;$i<=$mn;$i++) { return 0 if($possible[$a][$i] != $possible[$b][$i]); } return 1; } sub prettypos($) { my ($i)=@_; return sprintf "r%uc%u",1+$i/$mn,1+$i%$mn; } sub prettyrow($) { my ($i)=@_; return 1+$i/$mn; } sub prettycol($) { my ($i)=@_; return 1+$i%$mn; } sub prettyblock($) { my ($i)=@_; my $x=$i/($mn*$n); my $y=($i%$mn)/$m; return 1+$y+$n*$x; } sub prettyval($) { my ($v)=@_; my @vals=(undef,split //,$digitstring); die $v if($#vals<$v); return $vals[$v] if($vals[$v] eq $v); return "$vals[$v] ($v)"; } # Marks cells for which there is only one possible number # O($mn^3) sub pass1() { my ($i,$j,$v); my $found=0; return 0 if($skippass[1]); for($i=0;$i<$mn*$mn;$i++) { next if($puzzle[$i]); next unless(1==$possible[$i][0]); $v=(grep {$possible[$i][$_]} 1..$mn)[0]; print "The only possibility for cell ".prettypos($i)." is ".prettyval($v)."\n" if($showreasons); if($onlyhints) { print "Have you looked at the possibilities for ".prettypos($i)."?\n"; exit 0; } $found+=placenum($i,$v); } $passfound[1]+=$found; return $found; } # Marks cells for which it is the only possible location of a given number # O($mn^4) sub pass2() { my ($i,$v); my $found=0; return 0 if($skippass[2]); SQUARE: for($i=0;$i<$mn*$mn;$i++) { next if($puzzle[$i]); for($v=1;$v<=$mn;$v++) { next unless($possible[$i][$v]); unless(grep {$possible[$_][$v]} otherrow($i)) { print "The only place for ".prettyval($v)." in row ".prettyrow($i)." is ".prettypos($i)."\n" if($showreasons); if($onlyhints) { print "Have you looked at row ".prettyrow($i)."?\n"; exit 0; } $found+=placenum($i,$v); next SQUARE; } unless(grep {$possible[$_][$v]} othercol($i)) { print "The only place for ".prettyval($v)." in column ".prettycol($i)." is ".prettypos($i)."\n" if($showreasons); if($onlyhints) { print "Have you looked at column ".prettycol($i)."?\n"; exit 0; } $found+=placenum($i,$v); next SQUARE; } unless(grep {$possible[$_][$v]} otherblock($i)) { print "The only place for ".prettyval($v)." in block ".prettyblock($i)." is ".prettypos($i)."\n" if($showreasons); if($onlyhints) { print "Have you looked at block ".prettyblock($i)."?\n"; exit 0; } $found+=placenum($i,$v); next SQUARE; } } } $passfound[2]+=$found; return $found; } # O($mn^2) sub pass3helper($@) { my ($group,@set)=@_; my $found=0; my ($i,$v,@a,@b,@c,%skip); @a=grep {0==$puzzle[$_]} @set; while(@a) { @b=shift @a; foreach $i (@a) { push @b,$i if(samepossible($b[0],$i)); } die $group if($possible[$b[0]][0]<@b); next if(@b<$possible[$b[0]][0]); %skip=map {($_,1)} @b; @c=grep {0==$puzzle[$_] and not $skip{$_}} @set; next unless(@c); for($v=1;$v<=$mn;$v++) { next unless($possible[$b[0]][$v]); foreach $i (@c) { next unless($possible[$i][$v]); print "Tuplet ".join(", ",map {prettypos($_)} @b)." forbids ".prettyval($v)." for ".prettypos($i)."\n" if($showreasons); print "Tuple found in $group; continuing...\n" if($onlyhints); $found+=markimpossible($i,$v); } } } return $found; } # If it finds n mutually-related cells, each with the same set of # possible numbers, it marks those numbers as impossible for other # mutually-related cells # O($mn^3) sub pass3() { my $found=0; my $i; return 0 if($skippass[3]); foreach $i (samerow(0)) { $found+=pass3helper("column ".prettycol($i),samecol($i)); } foreach $i (samecol(0)) { $found+=pass3helper("row ".prettyrow($i),samerow($i)); } foreach $i (@blockstart) { $found+=pass3helper("block ".prettyblock($i),sameblock($i)); } $passfound[3]+=$found; return $found; } # O($mn^2) sub pass4helper1($@) { my ($group,@col)=@_; my $found=0; my ($i,$min,$max,$v,%skip); NUMBER: for($v=1;$v<=$mn;$v++) { $min=$mn+1; $max=0; foreach $i (0..$#col) { next NUMBER if($v==$puzzle[$col[$i]]); if($possible[$col[$i]][$v]) { $min=$i if($mn+1==$min); $max=$i; } } if($min/$n==$max/$n) { %skip=map {($_,1)} @col; foreach $i (sameblock($col[$min])) { next if($skip{$i}); next unless($possible[$i][$v]); print "Value ".prettyval($v)." only occurs in block ".prettyblock($col[$min])." of column ".prettycol($col[$min])." so it cannot be in ".prettypos($i)."\n" if($showreasons); print "Pass 4 found stuff in $group; continuing...\n" if($onlyhints); $found+=markimpossible($i,$v); } } } return $found; } # O($mn^2) sub pass4helper2($@) { my ($group,@row)=@_; my $found=0; my ($i,$min,$max,$v,%skip); NUMBER: for($v=1;$v<=$mn;$v++) { $min=$mn+1; $max=0; foreach $i (0..$#row) { next NUMBER if($v==$puzzle[$row[$i]]); if($possible[$row[$i]][$v]) { $min=$i if($mn+1==$min); $max=$i; } } if($min/$m==$max/$m) { %skip=map {($_,1)} @row; foreach $i (sameblock($row[$min])) { next if($skip{$i}); next unless($possible[$i][$v]); print "Value ".prettyval($v)." only occurs in block ".prettyblock($row[$min])." of row ".prettyrow($row[$min])." so it cannot be in ".prettypos($i)."\n" if($showreasons); print "Pass 4 found stuff in $group; continuing...\n" if($onlyhints); $found+=markimpossible($i,$v); } } } return $found; } # O($mn^2) sub pass4helper3($@) { my ($group,@block)=@_; my $found=0; my %skip=map {($_,1)} @block; my ($i,$col,$first,$row,$v); NUMBER: for($v=1;$v<=$mn;$v++) { $col=-1; $row=-1; $first=-1; foreach $i (0..$#block) { next NUMBER if($v==$puzzle[$block[$i]]); next unless($possible[$block[$i]][$v]); if(-1==$col and -1==$row) { $col=$block[$i]%$mn; $row=$block[$i]/$mn; $first=$i; } else { $col=-1 if($block[$i]%$mn != $col); $row=-1 if($block[$i]/$mn != $row); next NUMBER if(-1==$col and -1==$row); } } if(-1 != $col) { foreach $i (samecol($col)) { next if($skip{$i}); next if($puzzle[$i]); next unless($possible[$i][$v]); print "Value ".prettyval($v)." only occurs in column ".prettycol($block[$first])." of block ".prettyblock($block[$first])." so it cannot be in ".prettypos($i)."\n" if($showreasons); print "Pass 4 found stuff in $group; continuing...\n" if($onlyhints); $found+=markimpossible($i,$v); } } if(-1 != $row) { foreach $i (samerow($mn*$row)) { next if($skip{$i}); next if($puzzle[$i]); next unless($possible[$i][$v]); print "Value ".prettyval($v)." only occurs in row ".prettyrow($block[$first])." of block ".prettyblock($block[$first])." so it cannot be in ".prettypos($i)."\n" if($showreasons); print "Pass 4 found stuff in $group; continuing...\n" if($onlyhints); $found+=markimpossible($i,$v); } } } return $found; } # For each group, if all possibilities for an unplaced number are all in # some other group, mark that number as impossible for all other cells in # that other group # O($mn^3) sub pass4() { my ($i,$j,$v,@a,@b,@c,%skip); my $found=0; return 0 if($skippass[4]); foreach $i (samerow(0)) { $found+=pass4helper1("column ".prettycol($i),samecol($i)); } foreach $i (samecol(0)) { $found+=pass4helper2("row ".prettyrow($i),samerow($i)); } foreach $i (@blockstart) { $found+=pass4helper3("block ".prettyblock($i),sameblock($i)); } $passfound[4]+=$found; return $found; } # X-wing plus swordfish; look for rows (or columns) that have the same # columns (or rows) as the possibilities for a given number, and mark that # number as impossible for the remaining cells in those columns (or rows) # O($mn^4) sub pass5() { my $found=0; my ($i,$j,$k,$s,$v,%c,%r,%z); return 0 if($skippass[5]); for($v=1;$v<=$mn;$v++) { %c=(); %r=(); for($i=0;$i<$mn*$mn;$i++) { next unless($possible[$i][$v]); $c{$i%$mn}=[] unless($c{$i%$mn}); push @{$c{$i%$mn}},$i/$mn; $r{$i/$mn}=[] unless($r{$i/$mn}); push @{$r{$i/$mn}},$i%$mn; } %z=(); foreach $i (sort keys %c) { $s=join(",",@{$c{$i}}); $z{$s}=[] unless($z{$s}); push @{$z{$s}},$i; if(@{$z{$s}}==@{$c{$i}}) { foreach $j (@{$c{$i}}) { foreach $k (samerow($mn*$j)) { next if(grep {$_==$k%$mn} @{$z{$s}}); next unless($possible[$k][$v]); print "Value ".prettyval($v)." occurs in rows ".join(", ",map {prettyrow($mn*$_)} @{$c{$i}})." of columns ".join(", ",map {prettycol($_)} @{$z{$s}})." so it cannot be in ".prettypos($k)."\n" if($showreasons); print "Found X-wing or Swordfish dealing with ".prettypos($k)."; continuing...\n" if($onlyhints); $found+=markimpossible($k,$v); } } } } %z=(); foreach $i (sort keys %r) { $s=join(",",@{$r{$i}}); $z{$s}=[] unless($z{$s}); push @{$z{$s}},$i; if(@{$z{$s}}==@{$r{$i}}) { foreach $j (@{$r{$i}}) { foreach $k (samecol($j)) { next if(grep {$_==$k/$mn} @{$z{$s}}); next unless($possible[$k][$v]); print "Value ".prettyval($v)." occurs in columns ".join(", ",map {prettycol($_)} @{$r{$i}})." of rows ".join(", ",map {prettyrow($mn*$_)} @{$z{$s}})." so it cannot be in ".prettypos($k)."\n" if($showreasons); print "Found X-wing or Swordfish dealing with ".prettypos($k)."; continuing...\n" if($onlyhints); $found+=markimpossible($k,$v); } } } } } $passfound[5]+=$found; return $found; } # O(2^$mn) sub pass6helper($@) { my ($group,@set)=@_; my ($found,$i,$j,$v,@curposs,@used); @set=sort {$possible[$b][0]<=>$possible[$a][0]} grep {0==$puzzle[$_]} @set; return 0 unless(@set); @used=(); @curposs=(0); push @curposs,0 while($#curposs<$mn); $i=0; while(1) { die "$i-$#set" if($i>$#set); push @used,$i; last if($used[0]==$#set); for($v=1;$v<=$mn;$v++) { if($possible[$set[$i]][$v] and not $curposs[$v]) { $curposs[$v]=@used; $curposs[0]++; } } $i++; goto POP_IT if(@set<=$curposs[0]); if(@used==$curposs[0]) { $found=0; for($j=0;$j<@set;$j++) { next if(grep {$_==$j} @used); for($v=1;$v<=$mn;$v++) { next unless($curposs[$v]); next unless($possible[$set[$j]][$v]); print "The hidden subset ".join(", ",map {prettypos($set[$_])} @used)." forbids ".prettyval($v)." from occurring in ".prettypos($set[$j])."\n" if($showreasons); print "Found hidden subset in $group; continuing...\n" if($onlyhints); $found+=markimpossible($set[$j],$v); } } return $found if($found); $i=@set; # fall through to POP_IT } elsif($i>$#set) { # fall through to POP_IT } else { next; } POP_IT: $i=1+pop @used while($i>$#set); for($v=1;$v<=$mn;$v++) { if($curposs[$v]>@used) { $curposs[$v]=0; $curposs[0]--; } } } return 0; } # If it finds n mutually-related cells, each with a subset of the same # set of possible numbers, it marks those numbers as impossible for # other mutually-related cells # O($mn*2^$mn) sub pass6() { my $found=0; my ($i,@a); return 0 if($skippass[6]); foreach $i (samerow(0)) { $found+=pass6helper("column ".prettycol($i),samecol($i)); } foreach $i (samecol(0)) { $found+=pass6helper("row ".prettyrow($i),samerow($i)); } foreach $i (@blockstart) { $found+=pass6helper("block ".prettyblock($i),sameblock($i)); } $passfound[6]+=$found; return $found; } # XY-wing; look for three 2-possibility cells XY, YZ, and XZ, such that XY and # YZ are related and YZ and XZ are related, then mark X as impossible for all # cells related to both XY and XZ # O($mn^5) sub pass7() { my $found=0; my ($i,$j,$k,$l,$v1,$v2,$v3,%r); return 0 if($skippass[7]); for($i=0;$i<$mn*$mn;$i++) { next unless(2==$possible[$i][0]); ($v1,$v2)=grep {$possible[$i][$_]} 1..$mn; foreach $j (otherrow($i),othercol($i),otherblock($i)) { next unless(2==$possible[$j][0]); next unless($possible[$j][$v1]); ($v3)=grep {$possible[$j][$_] and $_ != $v1} 1..$mn; next if($v2==$v3); %r=map {($_,1)} otherrow($j),othercol($j),otherblock($j); foreach $k (otherrow($i),othercol($i),otherblock($i)) { next if($j==$k); next unless(2==$possible[$k][0]); next unless($possible[$k][$v2]); next unless($possible[$k][$v3]); foreach $l (otherrow($k),othercol($k),otherblock($k)) { next if($l==$i); next unless($r{$l}); next unless($possible[$l][$v3]); print "XY-wing across ".join(", ",map {prettypos($_)} $i,$j,$k)." forbids ".prettyval($v3)." from occurring at ".prettypos($l)."\n" if($showreasons); print "Found XY-wing dealing with ".prettypos($l)."; continuing...\n" if($onlyhints); $found+=markimpossible($l,$v3); } } } } $passfound[7]+=$found; return $found; } # Guess and check :( # O($mn^($mn*$mn)) my @guesshistory=(); sub pass9() { my ($found,$i,$v); my (@savedpuzzle,@savedpossible,@savedpassfound); return 0 if($skippass[$#skippass]); for($i=0;$i<$mn*$mn;$i++) { last unless($puzzle[$i]); } if($mn*$mn==$i) { return 0 unless($keepguessing); printboard(); print "\n"; die "never had to guess"; # This die is only visible if we didn't guess } if($onlyhints) { print "Had to resort to guessing\n"; exit 0; } for($v=1;;$v++) { if($mn+1==$v) { die "ran out of guesses"; # Only true on the final (important) die } next unless($possible[$i][$v]); @savedpuzzle=@puzzle; @savedpossible=map {[@$_]} @possible; @savedpassfound=@passfound; push @guesshistory,"$v\@$i"; if($stepbystep) { print "Pass 9 guesses $v at position $i:\n\n"; } elsif($showguesses) { print "Guessing ".join(", ",@guesshistory)."\n" } elsif($showreasons) { print "Guessing ".prettyval($v)." at ".prettypos($i)."\n"; } eval { close(STDERR); $found=placenum($i,$v); solveboard(); }; if($@) { if($stepbystep) { print "Guessing $v at position $i failed!\n\n"; } elsif($showguesses) { print "Guessing ".join(", ",@guesshistory)." FAILED\n"; } elsif($showreasons) { print "...but the guess of ".prettyval($v)." at ".prettypos($i)." didn't work\n"; } @puzzle=@savedpuzzle; @possible=@savedpossible; @passfound=@savedpassfound; pop @guesshistory; } else { $passfound[$#passfound]+=$found; pop @guesshistory; last; } } return $found; } sub parsecmdline() { my %opts=(); my $opts="12345679GHIKOabghnpqrsvw"; my $miniusage="usage: sudoku [-MN <#>] [-z ] [-$opts]"; unless(getopts("M:N:z:$opts",\%opts)) { print STDERR "$miniusage\n"; exit(1); } @skippass=(0,map {$opts{$_}} 1..7,9); $showguesses=$opts{G}; $onlyhints=$opts{H}; $keepguessing=$opts{K}; $m=($opts{M} or 3); $n=($opts{N} or 3); $mn=$m*$n; $noboard=$opts{q}; $nosolve=$opts{n}; $showstats=$opts{p}; $stepbystep=$opts{s}; $useasterisk=$opts{a}; $usebold=$opts{b}; $verbose=$opts{v}; $widemodein=($opts{w} or $opts{I}); $widemodeout=($opts{w} or $opts{O}); $showreasons=$opts{r}; if($opts{z}) { $digitstring=$opts{z}; $digitstring =~ s/(.)-(.)/join("","$1".."$2")/ges; } else { $digitstring=substr("123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0",0,$m*$n); } unless($m*$n==length($digitstring)) { print STDERR "You must provide exactly ",$m*$n," digits to be used\n"; exit(2); } if($opts{h}) { print <<"EOD"; $miniusage -1 skip pass 1 (one possible number for a given cell) -2 skip pass 2 (one possible cell for a given number) -3 skip pass 3 (identical doubles/triples/-tuples) -4 skip pass 4 (if all possibles in group1 in group2, kill others in group2) -5 skip pass 5 (X-wing/Swordfish) -6 skip pass 6 (doubles/triples/-tuples of subsets) -7 skip pass 7 (XY-wing) -9 skip pass 9 (guess-and-check) -G show guesses as they are being made -H only show hints for what to do next, but don't solve -I use wide mode on input: an extra space between each column -K if guessing succeeds, print the board and keep guessing (DANGEROUS!) -M <#> board has M blocks down and blocks have M cells across (default 3) -N <#> board has N blocks across and blocks have N cells down (default 3) -O use wide mode on output: an extra space between each column -a surround placed numbers with asterisks on big board (e.g., *3*) -b show placed numbers in bold on big board (e.g., 33) -h show this help message -n don't try to solve the board -p show statistics for the passes -q don't output any board (unless -v is given and board is unsolved) -r show reason for each marking -s show step-by-step progress -v show big board with possibilities for unsolved cells -w use wide mode: an extra space between each column -z use the characters in as the letters/numbers to be placed EOD exit(0); } } sub prettypossible($) { my ($i)=@_; my $retval=""; my $v=0; my $yep=0; my @out=(undef,split //,$digitstring); for($v=1;$v<=$mn+1;$v++) { if($possible[$i][$v]) { next if($yep); $yep=$v; } else { next unless($yep); if(2<($v-1)-$yep) { $retval.="$out[$yep]-$out[$v-1]"; } else { $retval.=join("",map {$out[$_]} $yep..($v-1)); } $yep=0; } } return $retval; } sub printboard() { my ($i,$j); my @out=($widemodeout?"_":" ",split //,$digitstring); for($i=0;$i<$mn;$i++) { for($j=0;$j<$mn;$j++) { print " " if($widemodeout and $j); print $out[$puzzle[$mn*$i+$j]]; } print "\n"; } } sub printposs() { my ($i,$j,$l,$s); $l=8*$m-1; my $blocksepline="-".(("-"x$l)."+")x$n; $blocksepline =~ s/\+$/\n/s; for($i=0;$i<$mn;$i++) { print $blocksepline if($i and 0==($i%$n)); for($j=0;$j<$mn;$j++) { print(($j and 0==($j%$m))?"|":" "); $s=prettypossible($mn*$i+$j); $s="*$s*" if($useasterisk and $puzzle[$mn*$i+$j]); if($usebold and $puzzle[$mn*$i+$j]) { $s=" $s\b$s"; $s.=" " if($j<$mn-1); } else { $s=" "x((7-length($s))/2).$s; $s.=" "x(7-length($s)) if($j<$mn-1); } print $s; } print "\n"; } } sub readfile() { my ($i,$j,$line,$val); for($i=0;$i<$mn;$i++) { die unless(defined($line=<>)); chomp $line; for($j=0;$j<$mn;$j++) { last unless(length $line); if($widemodein and $j) { die "Invalid character in widemode column: ".substr($line,0,1) if(" " ne substr($line,0,1)); $line=substr($line,1); last unless(length $line); } $val=1+index($digitstring,substr($line,0,1)); if($val) { $passfound[0]+=placenum($mn*$i+$j,$val); } elsif(substr($line,0,1) =~ /[^0 ._]/) { die "Invalid character in row ".($i+1)." column ".($j+1).": ".substr($line,0,1); } $line=substr($line,1); } } } sub solveboard() { my $found; if($stepbystep) { print "Start off:\n"; printposs(); print "\n"; while(1) { if(($found=pass1())) { print "Pass 1 marked off $found numbers:\n"; printposs(); print "\n"; next; } if(($found=pass2())) { print "Pass 2 marked off $found numbers:\n"; printposs(); print "\n"; next; } if(($found=pass3())) { print "Pass 3 marked off $found numbers:\n"; printposs(); print "\n"; next; } if(($found=pass4())) { print "Pass 4 marked off $found numbers:\n"; printposs(); print "\n"; next; } if(($found=pass5())) { print "Pass 5 marked off $found numbers:\n"; printposs(); print "\n"; next; } if(($found=pass6())) { print "Pass 6 marked off $found numbers:\n"; printposs(); print "\n"; next; } if(($found=pass7())) { print "Pass 7 marked off $found numbers:\n"; printposs(); print "\n"; next; } pass9(); # Handles $stepbystep on its own last; } } else { 1 while(pass1() or pass2() or pass3() or pass4() or pass5() or pass6() or pass7() or pass9()); } } # Checks board consistency; returns true iff the board is fully solved sub checkboard() { my $retval=1; my ($i,$j); for($i=0;$i<$mn*$mn;$i++) { if($puzzle[$i]) { die if(1 != $possible[$i][0]); foreach $j (otherrow($i),othercol($i),otherblock($i)) { die if($puzzle[$i]==$puzzle[$j]); die if($possible[$j][$puzzle[$i]]); } } else { $retval=0; } $j=0; map {$j++ if($possible[$i][$_])} 1..$mn; die unless($j==$possible[$i][0]); } return $retval; } parsecmdline(); initboard(); readfile(); solveboard() unless($nosolve); my $issolved=checkboard(); if($noboard) { printposs() if($verbose and not $issolved); } elsif($verbose) { printposs(); } else { printboard(); } if($showstats) { my $totalworktodo=$mn*$mn*$mn-$passfound[0]; $totalworktodo=1 unless($totalworktodo); print "Successes for each type of pass: ".join(", ",@passfound)." = ".(100*sum(@passfound[1..$#passfound])/$totalworktodo)."%\n"; } exit 1 if($noboard and not $issolved); 0;