#!/usr/bin/awk -f 
#
# GLOBAL VARIABLES:
#	grid		- Game grid
#	row		- Horizontal slice through the grid
#	col		- Vertical slice through the grid
#	sector		- solved numbers per sector
#	setorMap	- map of sector for each cell
#	solutions	- grid of all possible solutions per unsolved cell
#	solutionsCnt	- count of possible solutions for each unsolved number per sector
#

BEGIN { 
	for (i=1; i <= 9; i++ ) {
		for (j=1; j <= 9; j++ ) {
			grid[i,j]=0
			sectorMap[i,j]=toSector(i,j)
		}
	}


	"tput smso"	| getline SMSO
	"tput bold"	| getline BOLD
	"tput rmso"	| getline RMSO
	"tput clear"	| getline CLEAR
	"tput cup 0 0"	| getline HOME
	"tput cup 20 0"	| getline LINE20

	PROMPT = ">>"
	printf "%s ", PROMPT
}

$1 == "help" {
	print "help, load, loadFile, step, dumpsolutions, dumpSector, dumpSectorMap, dump"
}

$1 == "list" {
	LIST="ls puzzle.*"
	while ( LIST | getline listing >0 ) {
		print listing
	}
	close(LIST)
}

####################################################################
#
#	load puzzle from a file
#
####################################################################
$1 == "loadFile" {
	fileName = $2
	print "loading " fileName

	clearSector()
	delete grid
	delete row
	delete col

	r=0;
	while ( (getline < fileName) > 0 ) {
		r++
		for (c=1; c<=NF; c++)
		{
			if ( $c != ".")
				load(r, c, $c)
		}
	}

	close(fileName)
}

####################################################################
#
#	load puzzle from command line 
#
####################################################################
$1 == "load" {
	fileName=""
	for (i=2; i<=NF; i++)
	{
		split($i,fields,",")
		load(fields[1], fields[2], fields[3])
	}
}

####################################################################
#
#	step through automated solution of the puzzle
#
####################################################################
$1 == "step" {
	if (solveStep()==0)
		print "no solution"
	
}

####################################################################
#
#	automatically solve the entire puzzle
#
####################################################################
$1 == "solve" {
	
	printf "%s", CLEAR

	do {
		if ( $2 != "" ) {
			system("sleep " $2)
		}
		printf "%s", HOME

	} while (solveStep() != 0 ) 

	dump()
	print "Solution Stopped"
}

####################################################################
#
#	validate the currently solved puzzle against a solution
#	in a file
#
####################################################################
$1 == "check" {

	fileName=$2
	print "checking solution against " fileName

	r=0

	while ( (getline < fileName) > 0 ) {
		r++

		for (c=1; c<=NF; c++)
		{
			# print "grid["r","c"]("grid[r,c]")=" $c  ## DEBUG
			if (grid[r,c] != $c) {
				dump(r,c)
				print "Error @ cell " r","c
				close(fileName)
				next
			}
		}
	}

	print "Congradulations, your solution is correct!"

	close(fileName)
}

####################################################################
#
#	save the current puzzle in a file
#
####################################################################
$1 == "save"		{
	for (r=1; r<=9; r++) {
		for (c=1; c<=9; c++) {
			v = grid[r,c]
			if ( v <=0 )
				v="."
			printf "%s ", v  > $2
		}
		print "" > $2
	}
	close($2)
}

$1 == "dumpSolution"	{ dumpSolutions() }		# dump the list of solutions to output
$1 == "dumpSectorMap"	{ dumpSectorMap() }		# dump the sector map to output
$1 == "dumpSector"	{ dumpSectors() }		# dump all solved numbers per sector to output
$1 == "dump"		{ C=$3; dump($2, $3) }		# dump the puzzle grid to output
$1 == "quit"		{ exit 0 }			# exit the game
			{ printf "%s ", PROMPT }

####################################################################
#
#	load a value into a (r)ow and (c)olumn of the puzzle grid
#
####################################################################
function load( r, c, value) {
	grid[r,c]=value
	solutions[r,c]="C"
	row[r,value]=1
	col[c,value]=1
	addToSector(sectorMap[r, c],value)
}

####################################################################
#
#	attempt to find the first solvable cell in the grid.
#	print the grid with the solved cell highlighted.
#
####################################################################
function solveStep() {
	plotSolutions()

	for ( r=1; r<=9; r++ ) {
		for ( c=1; c<=9; c++ ) {
			for ( i=1; i <= 9; i++ ) {
				if(solutions[r,c] != "C" && solutions[r,c] ~ i && solutions[r,c] !~ /,/) {
					load(r,c,i)
					dump(r,c)
					print "                                   "
					return 1
				}
		
				if ( solutions[r,c]!="C" && solutions[r,c] ~ i && solutionsCnt[sectorMap[r,c],i]==1)
				{
					load(r,c,i)
					dump(r,c)
					print "                                   "
					return 1
				}
			}
		}
	}
	
        if ( !gridSolved() ) {
		plotSolutions()
		plotTwins()
		for ( r=1; r<=9; r++ ) {
			for ( c=1; c<=9; c++ ) {
				for ( i=1; i <= 9; i++ ) {
					if(solutions[r,c] != "C" && solutions[r,c] ~ i && solutions[r,c] !~ /,/) {
						load(r,c,i)
						dump(r,c)
						print "Solved using twins..."
						return 1
					}
			
					if ( solutions[r,c]!="C" && solutions[r,c] ~ i && solutionsCnt[sectorMap[r,c],i]==1)
					{
						load(r,c,i)
						dump(r,c)
						print "Solved using twins..."
						return 1
					}
				}
			}
		}
	}

	return 0
}

####################################################################
#
#	plot all possible solutions for all unsolved cells
#
####################################################################
function plotSolutions() {
	delete solutions
	delete solutionsCnt

	############################################################
	#
	#	Mark solved cells in the solution space
	#
	############################################################
	for ( r=1; r<=9; r++ ) {
		for (c=1; c<=9; c++) {
			if ( grid[r,c] != 0 ) {
				solutions[r,c]="C"
			}
		}
	}


	############################################################
	#
	#	plot all possible solutions for the current
	#	puzzle grid
	#
	############################################################
	for (i=1; i<=9; i++ ) {
		for ( r=1; r<=9; r++ ) {
			for ( c=1; c<=9; c++ ) {
				if ( solutions[r,c] != "C" ) {
					if ( row[r,i] != 1 && col[c,i] != 1 && sector[sectorMap[r,c]] !~ i) {
						if ( solutions[r,c] == 0 )
							solutions[r,c]=i
						else
							solutions[r,c]=solutions[r,c]","i

						solutionsCnt[sectorMap[r,c],i]= solutionsCnt[sectorMap[r,c],i]+1
					}
				}
			}
		}
	}
}

function plotTwins() {
	############################################################
	#
	#	look for "twins" in the solutions space
	#
	############################################################

	for ( r=1; r<=9; r++) {
		for ( c=1; c<=9; c++ ) {
			if (split(solutions[r,c],a,",") == 2 ) {
				if (matchTwinCol(r,c,a)) {
					extractTwinValuesFromCol(c,a)
				}

				if (matchTwinRow(r,c,a)) {
					extractTwinValuesFromRow(r,a)
				}
			}
		}
	}
}

function matchTwinCol(R,C,A){
	twinCount=0
	############################################################
	#
	#	look for "twins" across column in the solutions space
	#
	############################################################
	for ( ; C<=9; C++ ) {
		if (split(solutions[R,C],b,",") == 2 ) {
			if( isTwin(A,b) ) {
				twinCount++
			}
		}
	}

	if ( twinCount == 1 )
		return 1
	else
		return 0 #  false
}

function matchTwinRow(R,C,A){
	twinCount=0
	
	############################################################
	#
	#	look for "twins" across Row in the solutions space
	#
	############################################################
	for ( ; R<=9; R++ ) {
		if (split(solutions[R,C],b,",") == 2 ) {
			if( isTwin(A,b) ) {
				twinCount++
			}
		}
	}

	if ( twinCount == 1 )
		return 1
	else
		return 0 #  false
}

function extractTwinValuesFromCol(C, A) {
	for ( R=1; R<=9; R++ ) {
		if ( solutions[R,C] != "C" ) {
			split(solutions[R,C],B,",")

			if ( length(B) > 1 && !isTwin(A,B)) {
				solutions[R,C]=""

				for ( i=1; i<= length(B); i++ ) {
					if ( B[i] != A[1] && B[i] != A[2] ) {
						if ( solutions[R,C]=="" ) {
							solutions[R,C]=B[i]
						}else{
							solutions[R,C]=solutions[R,C]","B[i]
						}
					}
				}
			}
		}
	}
}

function extractTwinValuesFromRow(R, A) {
	for ( C=1; C<=9; C++ ) {
		if ( solutions[R,C] != "C" ) {
			split(solutions[R,C],B,",")

			if ( length(B) > 1 && !isTwin(A,B)) {
				solutions[R,C]=""

				for ( i=1; i<= length(B); i++ ) {
					if ( B[i] != A[1] && B[i] != A[2] ) {
						if ( solutions[R,C]=="" ) {
							solutions[R,C]=B[i]
						}else{
							solutions[R,C]=solutions[R,C]","B[i]
						}
					}
				}
			}
		}
	}
}

function isTwin(A, B) {
	if (  length(A) == 2 && length(B) == 2 && A[1] == B[1] && A[2] == B[2] ) {
		return 1
	}

	return 0
}

function gridSolved() {
	for ( r=1 ; r<=9; r++ ) {
		for ( c=1; c<=9; c++ ) {
			if ( solutions[r,c]!="C" )
				return 0
		}
	}
	return 1
}

####################################################################
#
#	dump the list of all currently plotted solutions for 
#	unsolved cells
#
####################################################################
function dumpSolutions() {
	for ( r=1; r<=9; r++ ) {
		for ( c=1; c<=9; c++ ) {
			printf "solutions[%d,%d]=%s\n", r, c, solutions[r,c]
		}
	}
}

####################################################################
#
#	dump all solved numbers per sector
#
####################################################################
function dumpSectors() {
	print "SECTORS {"
	for ( i=1; i <=9; i++ ) {
		printf "	Sector[%d]: %s\n", i, sector[i]
	}
	print "}"
}

####################################################################
#
#	map a cell to a sector
#
####################################################################
function toSector(r, c) {
	if ( r <= 3 && c <=3 ) {
		return 1
	} else if ( r <= 3 && c <=6 ) {
		return 2
	} else if ( r <= 3 && c <=9 ) {
		return 3
	} else if ( r <= 6 && c <=3 ) {
		return 4
	} else if ( r <= 6 && c <=6 ) {
		return 5
	} else if ( r <= 6 && c <=9 ) {
		return 6
	} else if ( r <= 9 && c <=3 ) {
		return 7
	} else if ( r <= 9 && c <=6 ) {
		return 8
	} else if ( r <= 9 && c <=9 ) {
		return 9
	}
}

####################################################################
#
#	dump the puzzle grid to output, highlight the cell 
#	designated by the (r)ow and (c)olumn arguments
#
####################################################################
function dump(r, c) {
	print fileName
	printf "===================\n"
	for (i=1; i<=9; i++ ) {
		printf "|"
		for ( j=1; j<=9; j++) {

			if( i==r && j==c) {
				SM=SMSO
				RM=RMSO
			}else{
				SM=""
				RM=""
			}

			if (grid[i,j]!=0) {
				printf "%s%d%s",SM,grid[i,j],RM
			}else{
				printf " "
			}

			if ( j%3 == 0 ) {
				printf "|"
			}else{
				printf ":"
			}
		}
		if ( i%3 == 0 ) {
			printf "\n|=====|=====|=====|\n"
		}else{
			printf "\n|-----|-----|-----|\n"
		}
	}
}

####################################################################
#
#	dump the pregenerated sector map to output
#
####################################################################
function dumpSectorMap() {
	printf "SECTOR MAP {\n	===================\n	"
	for (i=1; i<=9; i++ ) {
		printf "|"
		for ( j=1; j<=9; j++) {

			printf "%d", sectorMap[i,j]

			if ( j%3 == 0 ) {
				printf "|"
			}else{
				printf ":"
			}
		}
		if ( i%3 == 0 ) {
			printf "\n	|=====|=====|=====|\n	"
		}else{
			printf "\n	|-----|-----|-----|\n	"
		}
	}
	printf "\n}\n"
}

####################################################################
#
#	clear sector solutions
#
####################################################################
function clearSector() {
	delete sector
	delete sectorCnt
}

####################################################################
#
#	add a solution (v)alue to a (s)ector
#
####################################################################
function addToSector(s,v) {
	if ( sector[s]==0 ) {
		sector[s]=v
	} else{
		sector[s]=sector[s]","v
	}
	sectorCnt[s,v]=sectorCnt[s,v]+1
}

####################################################################
#
#	Program Exit
#
####################################################################
END { print ">> GOODBYE!" }