/*
	* ==============================================================================================
	The following copyrighted code is written and maintained by Michael Barron (mike@shannonandmike.net)
	* ----------------------------------------------------------------------------------------------
	You MAY NOT use this code in commercial products without direct written permission from me (Michael Barron).
	
	Creative Commons license (http://creativecommons.org/licenses/by-nc-sa/2.5)
	Attribution-NonCommercial-ShareAlike 2.5
	You are free:
	    - to copy, distribute, display, and perform the work
	    - to make derivative works

	ONLY under the following conditions:
		- Attribution: You must attribute the work in the manner specified by the author or licensor.
		- Noncommercial: You may not use this work for commercial purposes.
		- Share Alike: If you alter, transform, or build upon this work, you may distribute the resulting work only under a license identical to this one.

    For any reuse or distribution, you must make clear to others the license terms of this work and include this unmodified header.
    Any of these conditions can be waived if you get permission from the copyright holder.
	* ==============================================================================================
*/

var firstNineBits = 511;
var masterArray = new Array(9);
var cellArray = new Array(9);
var textboxArray = new Array(9);
var checkboxArray = new Array(9);
var validNums = '123456789';
var colCounts = new Array(9);
var rowCounts = new Array(9);
var clusterCounts = new Array(9);
var pointers;

function initAll() {
	for (var i = 0; i < 9; i++) {
		masterArray[i]   = new Array(9);
		cellArray[i]     = new Array(9);
		textboxArray[i]  = new Array(9);
		checkboxArray[i] = new Array(9);
		for (var j = 0; j < 9; j++) {
			masterArray[i][j]   = 0;
			cellArray[i][j]     = document.getElementById(i+'x'+j);
			textboxArray[i][j]  = document.getElementById(i+'x'+j+'t');
			checkboxArray[i][j] = document.getElementById(i+'x'+j+'c');
		}
	}
	for (var i = 0; i < 9; i++) {
		rowCounts[i]     = new Array(9);
		colCounts[i]     = new Array(9);
		clusterCounts[i] = new Array(9);
		for (var j = 0; j < 9; j++) {
			rowCounts[i][j] = 0;
			colCounts[i][j] = 0;
			clusterCounts[i][j] = 0;
		}
	}
	updatePuzzleToQuickEnter();
	updateAvailableNumbersLeft();
}

function removeAllSolutions() {
	// uncheck everything so that it will be cleared
	for (var i = 0; i < 9; i++) {
		for (var j = 0; j < 9; j++) {
			unlockCell(i,j);
		}
	}
	resetAndUpdate(true);
}

function updateQuickEnterToPuzzle() {
	var inc = document.getElementById('quickEnter').value;
	
	if (inc.length != 81) {
		alert('Error: There must be 81 numbers in the quick-enter box.');
	}
	else {
		var ch = 0;
		for (var row = 0; row < 9; row++) {
			for (var col = 0; col < 9; col++) {
				if (inc[ch] == '0') {
					unlockCell(row, col);
				}
				else {
					setCellSolution(row, col, inc[ch]);
					lockCell(row, col);
				}
				checkNumber(row, col);
				ch++;
			}
		}
	}
	document.getElementById('quickEnterButton').disabled = 'true';
	resetAndUpdate(false);
}

function updatePuzzleToQuickEnter() {
	resetAndUpdate(false);
	var rv = '';
	for (var row = 0; row < 9; row++) {
		for (var col = 0; col < 9; col++) {
			if (textboxArray[row][col].value == '') {
				rv += '0';
			}
			else {
				rv += textboxArray[row][col].value;
			}
		}
	}
	
	document.getElementById('quickEnter').value = rv;
	document.getElementById('quickEnterButton').disabled = 'true';
}

function setCellSolution(row, col, val) {
	textboxArray[row][col].value = val;
	masterArray[row][col] = ~Math.pow(2,val);
	updateRow(row, val);
	updateCol(col, val);
	updateCluster(row, col, val);
	textboxArray[row][col].style.background = "#E0FFE0";
}

function lockCell(row, col) {
	textboxArray[row][col].disabled = true;
	checkboxArray[row][col].checked = true;

	checkboxArray[row][col].style.display   = "inline";
	cellArray[row][col].style.background    = "#64b800";
	cellArray[row][col].style.padding       = "1px 1px 0px 1px";
	textboxArray[row][col].style.color      = "#000000";
	textboxArray[row][col].style.background = "#E0FFE0";
}

function unlockCell(row, col) {
	textboxArray[row][col].value    = '';
	textboxArray[row][col].disabled = false;
	checkboxArray[row][col].checked = false;

	checkboxArray[row][col].style.display   = "none";
	cellArray[row][col].style.background    = "#FFF6AA";
	cellArray[row][col].style.padding       = "1px 1px 1.2em 1px";
	textboxArray[row][col].style.color      = "#000000";
	textboxArray[row][col].style.background = "#FFFFFF";
}

// Called by the checkbox (when the user removes a "locked" number)
function openCellForInput(who) {
	var row = who.id.substring(0,1);
	var col = who.id.substring(2,3);
	unlockCell(row,col);
	resetAndUpdate(false);
}

function resetAndUpdate(overrideToggle) {
	// First clear out all of our non-finalized elements
	for (var row = 0; row < 9; row++) {
		for (var col = 0; col < 9; col++) {
			if (!checkboxArray[row][col].checked) {
				unlockCell(row, col);
				masterArray[row][col] = 0;
			}
		}
	}
	for (var row = 0; row < 9; row++) {
		for (var col = 0; col < 9; col++) {
			// It's a locked (known) value - update all cells around it
			if (checkboxArray[row][col].checked) {
				var val = textboxArray[row][col].value;
				updateRow(row, val);
				updateCol(col, val);
				updateCluster(row, col, val);
			}
		}
	}
	// Solve the puzzle as much as we can (if the user has auto-update turned on)
	if (document.getElementById('autoUpdateToggleCheckbox').checked || overrideToggle) {
		solvePuzzleLogical();
	}
	// Update the remaining numbers
	updateAvailableNumbersLeft();
}

function updateConstraints(who) {
	// Update the constraints attached to this newly entered digit (if we are locking this number)
	var row = who.id.substring(0,1);
	var col = who.id.substring(2,3);
	updateConstraintsRowCol(row, col);
	resetAndUpdate(false);
}

function updateConstraintsRowCol(row, col) {
	if (checkNumber(row, col)) {
		lockCell(row, col);
		// update the other affected cells in the row/col/cluster
		var val = textboxArray[row][col].value;
		updateRow(row, val);
		updateCol(col, val);
		updateCluster(row, col, val);
		if (document.getElementById('autoUpdateToggleCheckbox').checked) {
			solvePuzzleLogical();
		}
		updatePuzzleToQuickEnter();
	}
}

function solvePuzzleLogical() {
	var updateAll = true;
	while (updateAll) {
		while(solveSingleMissingNumbers()) { }
		updateAll = solveOnlyNumberLeft();
	}
}

function writeDebug(txt) {
	if (document.getElementById('debug')) {
		document.getElementById('debug').value += txt+"\n";
	}
}

function eliminateBasedOnSpaceLimitation(groupSize) {
	// Look for groups of X numbers spread across X locations.  If we find this, then we can say for certain
	// that the numbers must exist in these locations, and therefore CANNOT exist outside of these locations
	// for the given row/col/cluster.
	pointers    = new Array(groupSize);
	var oldBits = new Array(groupSize);

	// Initialize the pointer array
	for (var i = 0; i < groupSize; i++) {
		pointers[i] = i;
	}

	// Each iteration we test the X (== groupSize) number of elements to see if they represent X numbers.  If they do,
	// then the row/col/cluster is updated.
	// After the test on the current items being pointed to we increment the pointers.  The idea is to compare all
	// of the possible combinations.
	while (pointers[(groupSize-1)] < 9) {
		for (var i = 0; i < 9; i++) {
			var doRow = true;
			var doCol = true;
			var doCluster = true;
			// Only do the row/col/cluster if ALL of the pointers point to blank text boxes
			for (var p = 0; (p < groupSize); p++) {
				doRow = doRow && (textboxArray[i][pointers[p]].value == '');
				doCol = doCol && (textboxArray[pointers[p]][i].value == '');
				doCluster = doCluster && (textboxArray[getClusterRow(i, pointers[p])][getClusterCol(i, pointers[p])].value == '');
			}
			
			if (doRow || doCol || doCluster) {
				// Find the bits
				var rowBits = 0;
				var colBits = 0;
				var clusterBits = 0;
				// OR over the candidate locations for this col/row
				for (var p = 0; p < groupSize; p++) {
					rowBits |= masterArray[i][pointers[p]];
					colBits |= masterArray[pointers[p]][i];
					clusterBits |= masterArray[getClusterRow(i, pointers[p])][getClusterCol(i, pointers[p])];
				}

				try { ////
					// Check if we have solution for the row...
					if (doRow && (countBitsLeft(rowBits) == groupSize)) {
						// Save the old bit patterns (since they will be wiped out)
						for (var j = 0; j < groupSize; j++) {
							oldBits[j] = masterArray[i][pointers[j]];
						}
						// Remove the bit pattern from ALL the items in the row
						updateRow(i, rowBits);
						// Replace the bit patterns that are not supposed to change
						for (var j = 0; j < groupSize; j++) {
							masterArray[i][pointers[j]] = oldBits[j];
						}
					}
					// Check if we have solution for the col...
					if (doCol && (countBitsLeft(colBits) == groupSize)) {
						// Save the old bit patterns (since they will be wiped out)
						for (var j = 0; j < groupSize; j++) {
							oldBits[j] = masterArray[pointers[j]][i];
						}
						// Remove the bit pattern from ALL the items in the row
						updateCol(i, colBits);
						// Replace the bit patterns that are not supposed to change
						for (var j = 0; j < groupSize; j++) {
							masterArray[pointers[j]][i] = oldBits[j];
						}
					}
					// Check if we have solution for the cluster...
					if (doCluster && (countBitsLeft(clusterBits) == groupSize)) {
						// Save the old bit patterns (since they will be wiped out)
						for (var j = 0; j < groupSize; j++) {
							oldBits[j] = masterArray[getClusterRow(i, pointers[j])][getClusterCol(i, pointers[j])];
						}
						// Remove the bit pattern from ALL the items in the row
						updateCluster(getClusterRow(i, pointers[j]), getClusterCol(i, pointers[j]), clusterBits);
						// Replace the bit patterns that are not supposed to change
						for (var j = 0; j < groupSize; j++) {
							masterArray[getClusterRow(i, pointers[j])][getClusterCol(i, pointers[j])] = oldBits[j];
						}
					}

				} ////
				catch (e) {
					writeDebug("groupsize="+groupSize+" - "+i+","+pointers[p]+" ["+p+"]:"+getClusterRow(i, pointers[p])+";"+getClusterCol(i, pointers[p]));
				}
			}
		}
		// ---------------------------------------------------------------------------------
		// Increment the pointers...
		for (var p = (groupSize-1); p >= 0; p--) {
			if (incrementPointer(p, groupSize)) {
				break;
			}
		}
	}
}

// c = cluster number (0-8)
// i = cluster index (0-8)
function getClusterRow(c, i) {
	//writeDebug(c+","+i+": "+(3*Math.floor(c/3) + Math.floor(i/3)));
	return (3*Math.floor(c/3) + Math.floor(i/3));
}
function getClusterCol(c, i) {
	return (3*(c % 3) + (i % 3));
}

function incrementPointer(p, groupSize) {
	if (((groupSize-p)+pointers[p]) < 9) {
		pointers[p]++;
		return true;
	}
	else {
		// Reset the pointer to 2-after the previous pointer and move all future pointers to be in line after this pointer
		if (p == 0) {
			pointers[p]++;			
		}
		else {
			pointers[p] = pointers[(p-1)]+2;
		}		
		for (var p2 = (p+1); p2 < groupSize; p2++) {
			pointers[p2] = pointers[p2-1]+1;
		}		
		return false;
	}
}

function checkNumber(row, col) {
	var val = textboxArray[row][col].value;

	if ((val == '') || (val == ' ') || (val.length != 1)) {
		// do not prompt - that's annoying!
		unlockCell(row,col);
		return false;
	}
	if (validNums.indexOf(val.charAt(0)) < 0) {
		alert("You must enter a valid number (1-9).");
		unlockCell(row,col);
		return false;
	}
	// Make sure that this number is not already present in the row/col/cluster
	for (var c = 0; c < 9; c++) {
		if ((textboxArray[row][c].value == val) && (c != col)) {
			alert("You already have the number '"+val+"' in column "+(c+1)+" of this row.");
			unlockCell(row,col);
			return false;
		}
	}
	for (var r = 0; r < 9; r++) {
		if ((textboxArray[r][col].value == val) && (r != row)) {
			alert("You already have the number '"+val+"' in row "+(r+1)+" of this column.");
			unlockCell(row,col);
			return false;
		}
	}
	var startCol = 0;
	var startRow = 0;
	if (col > 2) { startCol = 3; }
	if (col > 5) { startCol = 6; }
	if (row > 2) { startRow = 3; }
	if (row > 5) { startRow = 6; }
	for (var i = startRow; i < startRow+3; i++) {
		for (var j = startCol; j < startCol+3; j++) {
			if ((textboxArray[i][j].value == val) && ((i != row) && (j != col))) {
				alert("You already have the number '"+val+"' in this 3x3 cluster.");
				unlockCell(row,col);
				return false;
			}
		}
	}
	return true;
}

function solveSingleMissingNumbers() {
	var rv = false;
	for (var i = 0; i < 9; i++) {
		for (var j = 0; j < 9; j++) {
			if (textboxArray[i][j].value == '') {
				if (isOnlyOneLeft(masterArray[i][j])) {
					var val = ((Math.log((~masterArray[i][j]) & firstNineBits) / Math.log(2))+1);
					setCellSolution(i, j, val);
					rv = true;
				}
			}
		}
	}
	return rv;
}

// This function MUST be run after the solveSingleMissingNumbers function has finished running completely
// (because it depends on the bits set on all cells).
function solveOnlyNumberLeft() {
	for (var i = 0; i < 9; i++) {
		for (var j = 0; j < 9; j++) {
			rowCounts[i][j] = 0;
			colCounts[i][j] = 0;
			clusterCounts[i][j] = 0;
		}
	}

	// Get row and col counts
	for (var row = 0; row < 9; row++) {
		for (var col = 0; col < 9; col++) {
			// Only check the unknown boxes
			if (textboxArray[row][col].value == '') {
				// Add a count for each possible number
				var bits = ((~masterArray[row][col]) & firstNineBits);
				for (var b = 0; b < 9; b++) {
					if (bits & Math.pow(2,b)) {
						rowCounts[row][b]++;
						colCounts[col][b]++;
					}
				}
			}
		}
	}

	// Get cluster counts
	var currentCluster = 0;
	for (var startI = 0; startI < 9; startI=startI+3) {
		for (var startJ = 0; startJ < 9; startJ=startJ+3) {
			for (var row = startI; row < startI+3; row++) {
				for (var col = startJ; col < startJ+3; col++) {
					if (textboxArray[row][col].value == '') {
						// Add a count for each possible number
						var bits = ((~masterArray[row][col]) & firstNineBits);
						for (var b = 0; b < 9; b++) {
							if (bits & Math.pow(2,b)) {
								clusterCounts[currentCluster][b]++;
							}
						}
					}
				}
			}
			currentCluster++;
		}
	}


	// Now search for a column or row (both i) that only has 1 available spot for a given number (we'll then need to find WHICH spot)
	for (var i = 0; i < 9; i++) {
		for (var n = 0; n < 9; n++) {
			if (rowCounts[i][n] == 1) {
				// Find the (only) cell in row i that can equal (n+1)
				var bitPattern = Math.pow(2,n);
				for (var j = 0; j < 9; j++) {
					if ((textboxArray[i][j].value == '') && (((~masterArray[i][j]) & firstNineBits) & bitPattern)) {
						// Ah-ha, we found the cell!
						setCellSolution(i, j, (n+1));
						return true;
					}
				}
			}
			if (colCounts[i][n] == 1) {
				// Find the (only) cell in col i that can equal (n+1)
				// NOTE THAT i AND j ARE INVERTED ON PURPOSE!!! - (i can be row or column, fyi)
				var bitPattern = Math.pow(2,n);
				for (var j = 0; j < 9; j++) {
					if ((textboxArray[j][i].value == '') && (((~masterArray[j][i]) & firstNineBits) & bitPattern)) {
						// Ah-ha, we found the cell!
						setCellSolution(j, i, (n+1));
						return true;
					}
				}
			}
			if (clusterCounts[i][n] == 1) {
				//alert("cluster "+i+" can have num "+(n+1)); //DEBUG
				// Find the (only) cell in cluster i that can equal (n+1)
				var rowStart = 0;
				var colStart = i;
				if (i > 2) {
					rowStart = 3;
					colStart = (i-3)*3;
				}
				if (i > 5) {
					rowStart = 6;
					colStart = (i-6)*3;
				}
				for (var k=rowStart; k < rowStart+3; k++) {
					for (var m=colStart; m < colStart+3; m++) {
						if ((textboxArray[k][m].value == '') && (((~masterArray[k][m]) & firstNineBits) & bitPattern)) {
							// Ah-ha, we found the cell!
							setCellSolution(k, m, (n+1));
							return true;
						}
					}
				}
			}
		}
	}
	return false;
}

function updateRow(row, val) {
	for (var col = 0; col < 9; col++) {
		masterArray[row][col] |= Math.pow(2,(val-1));
	}
}

function updateCol(col, val) {
	for (var row = 0; row < 9; row++) {
		masterArray[row][col] |= Math.pow(2,(val-1));
	}
}

function updateCluster(row, col, val) {
	var startCol = 0;
	var startRow = 0;
	if (col > 2) { startCol = 3; }
	if (col > 5) { startCol = 6; }
	if (row > 2) { startRow = 3; }
	if (row > 5) { startRow = 6; }
	for (var i = startRow; i < startRow+3; i++) {
		for (var j = startCol; j < startCol+3; j++) {
			masterArray[i][j] |= Math.pow(2,(val-1));
		}
	}
}

function isOnlyOneLeft(bits) {
	// If it's a blank slate, then of course it's not final
	if (bits == 0) {
		return false;
	}
	// Check if we've only got 1 unknown bit left...
	bits = (~bits) & firstNineBits;
	for (var i = 0; i < 9; i++) {
		if (bits == Math.pow(2,i)) {
			return true;
		}
	}
	return false;
}

function countBitsLeft(bits) {
	rv = 0;
	// Everything is possible... mm, k!
	if (bits == 0) {
		return 9;
	}
	// Check if we've only got 1 unknown bit left...
	bits = (~bits) & firstNineBits;
	for (var i = 0; i < 9; i++) {
		if (bits & Math.pow(2,i)) {
			rv++;
		}
	}
	return rv;
}

function updateAvailableNumbersLeft() {
	for (var i = 0; i < 9; i++) {
		for (var j = 0; j < 9; j++) {
			var newTitle = '[None]';
			var bitsLeft = countBitsLeft(masterArray[i][j]);
			if (bitsLeft > 0) {
				newTitle = 'Possible: ';
				var bits = (~masterArray[i][j]) & firstNineBits;
				for (var k = 0; k < 9; k++) {
					if (bits & Math.pow(2,k)) {
						newTitle += (k+1);
						if(--bitsLeft > 0) {
							newTitle += ', ';
						}
					}
				}				
			}
			else if (textboxArray[i][j].value == '') {
				// We've got a problem - no solution is entered, nor does one exist!
				cellArray[i][j].style.background    = "#FF0000";
				textboxArray[i][j].style.color      = "#FFFFFF";
				textboxArray[i][j].style.background = "#FF0000";
			}
			textboxArray[i][j].title = newTitle;
		}
	}
}

function autoUpdateToggle(chkbox) {
	resetAndUpdate(false);
}
											
/*
function solvePuzzleBruteForce() {
	// First try to trim down the number of possible values for each square (can greatly reduce computing time)
	for (var groupSize = 2; groupSize < 5; groupSize++) {
		eliminateBasedOnSpaceLimitation(groupSize);
		solvePuzzleLogical();
	}	
	
	// Now solve using brute force.  Start with the indexes that have the fewest possibilities and
	// fill in answers - if we reach a point where no numbers are available back out and follow another
	// branch of the search tree.
	
	// First, collect all the unsolved squares and sort them in ascending order (based on number of possible solutions left)
	
	// Substitute a solution and attempt to solve logically.  FAIL at any point that squares have no values left available.
}
*/