#!/usr/bin/env perl

#*************************************************
#** Verify a MiniSAT solution for Sudoku puzzle **
#*************************************************

my $valid = -1;

while (<>) {
	my $line = $_;
	my @grid;
	for($i = 0; $i < 9; $i++ ){
		for($j = 0; $j < 9; $j++ ){
			$grid[$i][$j] = 0;
		}
	}

	#Grabs a solution line
	if($line =~ m/^\s*(-?\d+\s+)+(-?\d+\s*)$/)
	{
		$valid = 1;
		my @literals = split /\s+/, $line;
		#breaks line up into array of literals
		foreach $lit (@literals){
			#ignore unused literals
			if(!($lit =~ m/[0-]/) && length($lit) == 3)
			{
				my $i = substr($lit, 0, 1);
				my $j = substr($lit, 1, 1);
				my $k = substr($lit, 2, 1);
				#fill in grid and check if duplicates occur
				if($grid[$i-1][$j-1]==0)
				{
					$grid[$i-1][$j-1]=$k;
				}
				else
				{
					$valid = 0;
					print "INVALID, two values assigned to cell $i, $j\n";
				}
			}
		}

		my %digits;

		#verify rows
		for($i = 0; $i < 9; $i++ ){
			%digits=();
			for($j = 0; $j < 9; $j++ ){
				if($grid[$i][$j] =~ m/[1-9]/){
					$digits{$grid[$i][$j]} = 1;
				}
			}
			#check if there are 9 unique digits
			if(scalar(keys %digits)!=9)
			{
				$valid = 0;
				print "INVALID, not all values present in row ".($i+1)."\n";
			}
		}

		#verify columns
		for($j = 0; $j < 9; $j++ ){
			%digits=();
			for($i = 0; $i < 9; $i++ ){
				if($grid[$i][$j] =~ m/[1-9]/){
					$digits{$grid[$i][$j]} = 1;
				}
			}
			#check if there are 9 unique digits
			if(scalar(keys %digits)!=9)
			{
				$valid = 0;
				print "INVALID, not all values present in column ".($j+1)."\n";
			}
		}

		#verify boxes
		for($r = 0; $r < 3; $r++ ){
		for($s = 0; $s < 3; $s++ ){
			%digits=();
			for($i = 0; $i < 3; $i++ ){
			for($j = 0; $j < 3; $j++ ){
				if($grid[3*$r+$i][3*$s+$j] =~ m/[1-9]/){
					$digits{$grid[3*$r+$i][3*$s+$j]} = 1;
				}
			}
			}
			#check if there are 9 unique digits
			if(scalar(keys %digits)!=9)
			{
				$valid = 0;
				print "INVALID, not all values present in box $r, $s\n";
			}
		}
		}

		if($valid==1)
		{
			print "VALID solution\n"
		}

		#print grid
		print "----------------\n  ";
		for($i = 0; $i < 9; $i++ ){
			for($j = 0; $j < 9; $j++ ){
				print "$grid[$i][$j]";
				if($j % 3 == 2)
				{
					print " ";
				}
			}
			print "\n  ";
			if($i % 3 == 2)
			{
				print "\n  ";
			}
		}
	}
}

if($valid==-1)
{
	print "INVALID, no solution found in file.\n"
}