/* Algorithm for solving a Sudoku puzzle:
 *
 * 1. Store a 9x9 array of the puzzle, build a 9x9 array
 *    containing the values 1 through 9.  These are the
 *    possible choices for each cell.
 *
 *    T. Check the row, column, and box for each element in
 *       the choices array, to see if any do not belong.  If
 *       so, remove them.  If an element has only one
 *       possible value, then place it in the puzzle, it must
 *       be correct.
 *       * During this stage, keep a tally on the puzzle
 *         element with the least number of choices
 *       Return the location and choices for the element with
 *       the smallest nonempty set of choices.  If the puzzle
 *       is full, return a flag stating this
 *
 * 2. Call function T until there are no cells with just one
 *    choice remaining.  
 *    2.1 If it is full, check for accuracy.
 *        2.1.1 If it is accurate, return true flag and puzzle
 *        2.1.2 Else return error flag
 *    2.2 Else proceed to step 3.
 *
 * 3. (Optional) Shuffle the choice array for the element with
 *    the fewest choices.
 * 
 * 4. For i=1 to number of choices
 *        Copy puzzle and choices 9x9 arrays
 *        Place choice i in the slot
 *        If contradition, next i
 *        Call step 2
 *            If returned true flag and full correct board, return this information
 *            Else, next i
 *
 * (I am aware that this is not the greatest algorithm.)
 * 
 * The returned value from the base function should be the correct puzzle.
 * See solvePuzzle for more details.
 */


// Checks if a puzzle has all cells filled in
// Returns false if empty cells exist
function completeCheck(puzzle) {
	var i, j;
	for(i=0; i<9; i++) for(j=0; j<9; j++) if(isNaN(puzzle[i][j])) return false;
	return true;
}


// Returns choices array: a 9x9x9 (initially) array which
// contains all possible choices for each cell.
function getChoices(puzzle) {
	var i, j;
	var choices = new Array();
	
	for(i=0; i<9; i++) {
		choices[i] = new Array();
		for(j=0; j<9; j++) {
			choices[i][j] = new Array();
			if(!isNaN(puzzle[i][j])) choices[i][j].length = 0;
			else {
				var k;
				for(k=0; k<9; (choices[i][j][k] = ++k));
			}
		}
	}
	
	return choices;
}


// Returns true if val is contained in the row row, false otherwise
function rowContains(puzzle, row, val) {
	var i;
	for(i=0; i<9; i++) if(puzzle[row][i] == val) return true;
	return false;
}


// Returns true if val is contained in the column col, false otherwise
function colContains(puzzle, col, val) {
	var i;
	for(i=0; i<9; i++) if(puzzle[i][col] == val) return true;
	return false;
}


// Returns true if the box containing cell (row, col) contains val, false otherwise
function boxContains(puzzle, row, col, val) {
	var i, j;
	for(i=Math.floor(row/3)*3; i<Math.floor((row+3)/3)*3; i++)
		for(j=Math.floor(col/3)*3; j<Math.floor((col+3)/3)*3; j++)
			if(puzzle[i][j] == val) return true;
	return false;
}


// Function "T" in the algorithm.
// Places trivial items in their cells.
// Returns index of first cell with lowest nonzero quantity of choices.
// Note that puzzle and choices are passed as references, so will not be returned.
function choiceCompress(puzzle, choices) {
	var i, j, k;
	var mini=-1, minj=-1, minc=10;
	
	// Remove all invalid choices
	for(i=0; i<9; i++) for(j=0; j<9; j++) {
		for(k=0; k<choices[i][j].length; k++) {
			if(rowContains(puzzle, i, choices[i][j][k])
			|| colContains(puzzle, j, choices[i][j][k])
			|| boxContains(puzzle, i, j, choices[i][j][k])) {
				choices[i][j].splice(k, 1);
				--k;
			}
		}
		
		if(choices[i][j].length > 0 && choices[i][j].length < minc) {
			mini = i;
			minj = j;
			minc = choices[i][j].length;
		}
	}
	
	return Array(mini, minj);
}


// Places all trivial values into the puzzle
function placeTrivialValues(puzzle, choices) {
	var i, j;
	for(i=0; i<9; i++) for(j=0; j<9; j++) if(choices[i][j].length == 1) 
		puzzle[i][j] = choices[i][j][0];
	updateTableProxy(puzzle);
}


// Returns true if the puzzle contains contradictions, false otherwise
// If quitOnNan is true, then it will return true if a NaN is encountered
function containsContradictions(puzzle, quitOnNan) {
	var i, j, k, l;
	for(i=0; i<9; i++) for(j=0; j<9; j++) {
		var v = puzzle[i][j];
		if(isNaN(v)) {
			if(quitOnNan) return true;
			else continue;
		}
		
		// Check the row for errors
		for(k=i+1; k<9; k++) if(puzzle[k][j] == v) {
			return true;
		}
		
		// Check for column errors
		for(k=j+1; k<9; k++) if(puzzle[i][k] == v) {
			return true;
		}
		
		// Check for box errors
		for(k=Math.floor(i/3)*3; k<Math.floor((i+3)/3)*3; k++) {
			for(l=Math.floor(j/3)*3; l<Math.floor((j+3)/3)*3; l++) {
				if(k == i && l == j) continue;
				if(puzzle[k][l] == v) {
					return true;
				}
			}
		}
	}
	
	return false;
}




// Step 2 for the solve algorithm
// Returns true if solved, false otherwise, as well as puzzle if correct
function solveStep2(puzzle, choices) {
	while(1) {
		var i, j, min;
		var r = choiceCompress(puzzle, choices);
		i = r[0];
		j = r[1];
		
		if(i < 0) {
			// The puzzle is full
			return Array(!containsContradictions(puzzle, true), puzzle);
		}
		
		min = choices[i][j].length;
		if(min == 1) {
			placeTrivialValues(puzzle, choices);
			//updateTableProxy(puzzle);
			continue;
		}
		else if(min <= 9) {
			// We need to guess
			// Step 3: Shuffle the choices
			//choices[i][j].sort(function() { return 0.5-Math.random(); });
			
			// Step 4
			var k;
			for(k=0; k<min; k++) {
				// Copy puzzle and choices;
				var pcopy = new Array(); 
				var ccopy = new Array();
				
				var m, n;
				for(m=0; m<9; m++) {
					pcopy[m] = new Array();
					ccopy[m] = new Array();
					for(n=0; n<9; n++) {
						var l;
						pcopy[m][n] = puzzle[m][n];
						ccopy[m][n] = new Array();
						for(l=0; l<choices[m][n].length; l++) ccopy[m][n][l] = choices[m][n][l];
					}
				}
				
				// Place choice k in the slot
				do {
					pcopy[i][j] = choices[i][j][k];
					if(++k >= min) break;
				} while(containsContradictions(pcopy, false)) 
				--k;
				ccopy[i][j].length = 0;
				
				var solved, pp;
				updateTableProxy(pcopy);
				var r = solveStep2(pcopy, ccopy);
				solved = r[0];
				pp = r[1];
				if(solved) return Array(solved, pp);
			}
			
			return Array(false, puzzle);
		}
	}
}


// A disgusting busy wait
function wait(ms) {
	var date = Date();
	var curDate;
	
	do{
		curDate = Date();
	} while(curDate - date < ms);
}


// Updates the table with the current puzzle
function updateTable(puzzle) {
	var i, j;
	for(i=1; i<=9; i++) for(j=1; j<=9; j++) {
		var cell = document.getElementById("c" + i + j);
		cell.value = isNaN(puzzle[i-1][j-1])? "": puzzle[i-1][j-1];
	}
}


// Makes the tables animate nicely in certain non-Firefox browsers
function updateTableProxy(puzzle) {
	//wait(100);
	updateTable(puzzle);
}


// Solves the puzzle for you
function solvePuzzle() {
	// Step 1: Store puzzle and cell choices in arrays
	var puzzle = getPuzzle();
	var choices = getChoices(puzzle);
	
	
	// Step 2: 
	var solved;
	var r = solveStep2(puzzle, choices);
	solved = r[0];
	puzzle = r[1];
	
	
	// Finally: Put it back in the table
	updateTable(puzzle);
	
	return solved;
}