#!/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>,<poss1?>,<poss2?>,...,<poss$mn?>].
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 <n>
# 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 <n> rows (or columns) that have the same <n>
# columns (or rows) as the <n> 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 <n> 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 <string>] [-$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/<n>-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/<n>-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 <s>  use the characters in <s> 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;