#!/usr/bin/perl -w
use strict;
use integer;
use Getopt::Std;

# Boards are read from stdin or as filename on the command line.
# Board format is 21 lines, with space or a digit in each location.
# Trailing characters on each line are optional.

# Holds solved cells in an 441-element array
my @puzzle;

my ($helpercmd,$nosolve,$noboard,$widemodein,$widemodeout);

sub initboard() {
	my $i;

	@puzzle=();
	for($i=0;$i<441;$i++) {
		$puzzle[$i]=0;
	}
}

sub placenum($$) {
	my ($i,$val)=@_;

	die if($puzzle[$i]);
	$puzzle[$i]=$val;
}

sub parsecmdline() {
	my %opts=();
	my $opts="1234567IOhnqw";

	unless(getopts($opts,\%opts)) {
		print STDERR "usage: sudoku [-$opts]\n";
		exit(1);
	}
   my $skippasses=join("",grep {$opts{$_}} 1..7);
   $helpercmd="sudoku -9$skippasses";
	$nosolve=$opts{n};
	$noboard=$opts{q};
	$widemodein=($opts{w} or $opts{I});
	$widemodeout=($opts{w} or $opts{O});
	if($opts{h}) {
		print <<"EOD";
usage: sudoku [-$opts]
   -#  don't use pass <#> (pass 9, guess-and-check, is never used)
   -I  use wide mode on input: an extra space between each column
   -O  use wide mode on output: an extra space between each column
   -h  show this help message
   -n  don't try to solve the board
   -q  don't output any board (unless -v is given and board is unsolved)
   -w  use wide mode: an extra space between each column
EOD
		exit(0);
	}
}

sub mustbewhite($) {
	my ($i)=@_;
	my $row=$i/21;
	my $col=$i%21;
	return 1 if((9<=$col and $col<12) and ($row<6 or 15<=$row));
	return 1 if((9<=$row and $row<12) and ($col<6 or 15<=$col));
	return 0;
}

sub printboard() {
	my ($i,$j);

	for($i=0;$i<21;$i++) {
		for($j=0;$j<21;$j++) {
			print " " if($widemodeout and $j);
			if(mustbewhite(21*$i+$j)) {
				print " ";
			} else {
				print $puzzle[21*$i+$j]?$puzzle[21*$i+$j]:$widemodeout?"_":" ";
			}
		}
		print "\n";
	}
}

sub readfile() {
	my ($i,$j,$line);

	for($i=0;$i<21;$i++) {
		die unless(defined($line=<>));
		chomp $line;
		for($j=0;$j<21;$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);
			}
			if(substr($line,0,1) =~ /[1-9]/) {
				die "Digit in whitespace-required area at r".($i+1)."c".($j+1) if(mustbewhite($i*21+$j));
				placenum(21*$i+$j,substr($line,0,1));
			} elsif(substr($line,0,1) =~ /[^0 ._]/) {
				die "Invalid character in board: ".substr($line,0,1);
			}
			$line=substr($line,1);
		}
	}
}

sub invokehelper($) {
	my ($offset)=@_;
	my $old="";
	my $found=0;
	my ($i,$j,$new);

	for($i=0;$i<9;$i++) {
		for($j=0;$j<9;$j++) {
			$old.=$puzzle[21*$i+$j+$offset]?$puzzle[21*$i+$j+$offset]:" ";
		}
		$old.="\n";
	}
	$new=`echo '$old'|sudoku -9`;
   die unless(defined $new and 90==length($new));
	for($i=0;$i<90;$i++) {
		if(substr($old,$i,1) ne substr($new,$i,1)) {
			placenum(21*($i/10)+($i%10)+$offset,substr($new,$i,1));
			$found++;
		}
	}
	return $found;
}

sub solveboard() {
	my $keepgoing;

	do {
		$keepgoing=0;
		$keepgoing+=invokehelper(0);
		$keepgoing+=invokehelper(12);
		$keepgoing+=invokehelper(132);
		$keepgoing+=invokehelper(252);
		$keepgoing+=invokehelper(264);
	} while($keepgoing);
}

# Returns true iff the board is fully solved
sub issolved() {
	my $retval=1;
	my ($i,$j);

	for($i=0;$i<441;$i++) {
		next if(mustbewhite($i));
		return 0 unless($puzzle[$i]);
	}
	return 1;
}

initboard();
parsecmdline();
readfile();
solveboard() unless($nosolve);
my $issolved=issolved();
printboard() unless($noboard);
exit 1 if($noboard and not $issolved);
0;