/**
 * sudoku.js
 * version 0.3
 * By Tim Down
 * Last modified: 14/3/2006.
 *
 * Simple Sudoku solver. It uses six simple strategies to solve a puzzle by
 * pure deduction, and if this is not completely successful then it resorts 
 * to recursively guessing values and applying deduction until all possible
 * solutions are found.
 *
 * The nice feature of this solver is the record it keeps of its working,
 * which the use can step through and see the partially completed puzzle
 * at each step.
 */

/* ------------------------------------------------------------------------ */

function SudokuGrid(containerElement, logElement) {
	var squareCompletionType = {
		INITIAL_VALUE_SAVED: 1,
		INITIAL_VALUE_USER: 2,
		AFTER_SOME_SOLVER_ACTION: 3,
		ONLY_VALUE_FOR_SQUARE: 4,
		ONLY_SQUARE_FOR_VALUE: 5,
		GUESSED_VALUE: 6,
		CONDITIONAL_ON_GUESS: 8
	};
	
	var grid = this;
	this.containerElement = containerElement;
	this.logElement = logElement;
	this.currentSquare = null;

	this.init = function() {
		// Draw grid, making concessions for IE's absurd reluctance to display
		// table elements dynamically created via standard DOM methods
		var table = this.containerElement.appendChild(document.createElement("table"));
		table.cellPadding = 0;
		table.cellSpacing = 0;
		table.className = "sudoku";
		
		var tbody = table.appendChild(document.createElement("tbody"));
		for (var r = 0; r < 3; r++) {
			var tr = tbody.appendChild(document.createElement("tr"));
			for (var c = 0; c < 3; c++) {
				// Add minigrid
				var td = tr.appendChild(document.createElement("td"));
				var mg_table = td.appendChild(document.createElement("table"));
				mg_table.cellSpacing = 0;
				mg_table.className = "minigrid";
				var mg_tbody = mg_table.appendChild(document.createElement("tbody"));
				for (var mg_r = 0; mg_r < 3; mg_r++) {
					var mg_tr = mg_tbody.appendChild(document.createElement("tr"));
					for (var mg_c = 0; mg_c < 3; mg_c++) {
						// Create individual cell
						var mg_td = mg_tr.appendChild(document.createElement("td"));
						mg_td.className = "square";
						var possibilitiesDiv = mg_td.appendChild(document.createElement("div"));
						possibilitiesDiv.className = "possibilities";
						var input = mg_td.appendChild(document.createElement("input"));
						input.maxLength = 1;
						input.size = 1;
					}
				}
			}
		}
		
		// IE will not be displaying the grid at this point, so it is necessary to get it
		// displayed by force
		this.containerElement.innerHTML = this.containerElement.innerHTML;
		
		// Note: the above line has destroyed all the above references to DOM
		// objects, so we have to create new refernces from the DOM tree
		
		// Now set up the squares as objects event handlers on the inputs
		this.squares = new Array(9);
		for (var row = 0; row < 9; row++) {
			this.squares[row] = new Array(9);
		}
		table = this.containerElement.lastChild;
		for (r = 0; r < 3; r++) {
			tr = table.rows[r];
			for (c = 0; c < 3; c++) {
				// Obtain the minigrid and extract squares from it
				mg_table = tr.cells[c].firstChild;
				for (var mg_r = 0; mg_r < 3; mg_r++) {
					mg_tr = mg_table.rows[mg_r];
					for (var mg_c = 0; mg_c < 3; mg_c++) {
						// Obtain individual square
						mg_td = mg_tr.cells[mg_c];
						possibilitiesDiv = mg_td.getElementsByTagName("div")[0];
						input = mg_td.getElementsByTagName("input")[0];
						row = 3 * r + mg_r;
						column = 3 * c + mg_c;
						this.squares[row][column] = new Square(row, column, mg_td, input, possibilitiesDiv);
					}
				}
			}
		}
		
		// Add key handlers for arrow keys
		table.onkeydown = function(e) {
			var evt = e ? e : event;
			if (grid.currentSquare) {
				var row = grid.currentSquare.row;
				var column = grid.currentSquare.column;
				var cursor = false;
				switch (evt.keyCode) {
					// Left
					case 37:
						cursor = true;
						if (column == 0) {
							column = 8;
							row = (row == 0) ? 8 : row - 1;
						} else {
							column = column - 1;
						}
						break;
					// Up
					case 38:
						cursor = true;
						row = (row == 0) ? 8 : row - 1;
						break;
					// Right
					case 39:
						cursor = true;
						if (column == 8) {
							column = 0;
							row = (row == 8) ? 0 : row + 1;
						} else {
							column = column + 1;
						}
						break;
					// Down
					case 40:
						cursor = true;
						row = (row == 8) ? 0 : row + 1;
						break;
				}
				if (cursor) {
					grid.squares[row][column].input.focus();
					grid.squares[row][column].input.select();
				}
			}
		};
	}
	
	this.setState = function(state) {
		this.state = state;
		this.updateDisplay();
	};
	
	this.getSerializedState = function() {
		return this.state.toSource();
	};

	this.showSerializedState = function() {
		prompt("Copy the text below. You can load a puzzle later with this text", this.getSerializedState());
	};
	
	this.clearPuzzle = function() {
		this.stateInvalidated = false;
		this.doneAnySolving = false;
		logger.clear();
		this.setState(new SudokuState());
	};
	
	this.updateDisplay = function() {
		this.state.actOnAllValues(
			function(row, column, value) {
				var square = grid.squares[row][column];
				square.unhighlight();
				if (grid.state.hasValue(row, column)) {
					square.setValue(value, true, grid.state.completionTypes[row][column]);
				} else {
					square.clearValue();
				}
				square.setPossibleValues(grid.state.possibleValues[row][column]);
			}
		);
	};
	
	this.loadPuzzle = function(puzzle) {
		if (this.checkState()) {
			this.clearPuzzle();
			if (typeof puzzle == "string") {
				for (var r = 0; r < this.squares.length; r++) {
					var rowFirstCharIndex = r * this.squares[r].length;
					for (var c = 0; c < this.squares[r].length; c++) {
						var val = puzzle.charAt(rowFirstCharIndex + c);
						if (val && val != "0") {
							var square = this.squares[r][c];
							square.setValue(parseInt(val), true, false, squareCompletionType.INITIAL_VALUE_SAVED);
						}
					}
				}
			} else {
				for (var i = 0; i < puzzle.length; i++) {
					try {
						var square = this.squares[puzzle[i][0] - 1][puzzle[i][1] - 1];
						square.setValue(puzzle[i][2], true, false, squareCompletionType.INITIAL_VALUE_SAVED);
					} catch (ex) {
						alert(puzzle[i][0] + ", " + puzzle[i][1]);
					}
				}
			}
		}
	};
	
	this.solve = function() {
		//alert(this.state.toSource());
		this.stateInvalidated = false;
		logger.clear();
		this.solver.setState(this.state);
		this.solver.solve();
		this.doneAnySolving = true;
		this.selectFirstLogEntry();
	};
	
	this.nextLogEntry = function() {
		if (this.checkState()) {
			logger.nextEntry(true);
		}
	};

	this.previousLogEntry = function() {
		if (this.checkState()) {
			logger.previousEntry(true);
		}
	};

	this.selectFirstLogEntry = function() {
		if (this.checkState()) {
			logger.selectFirstEntry();
		}
	};
	
	this.checkState = function() {
		if (this.stateInvalidated) {
			return confirm("You have made changes to the grid. If you continue your changes will be lost. Are you sure you want to continue?");
		}
		return true;
	};
	
	/* --------------------------------------------------------------------- */

	function Square(row, column, container, input, possibilitiesDiv) {
		this.row = row;
		this.column = column;
		this.container = container;
		this.input = input;
		this.possibilitiesDiv = possibilitiesDiv;
		
		var square = this;
		this.input.onchange = function() {
			if (this.value == "" && square.hasValue()) {
				grid.stateInvalidated = true;
				square.clearValue();
			} else if (/[0-9]/.test(this.value) && this.value != square.getValue()) {
				square.setValue(this.value, false, grid.doneAnySolving ? squareCompletionType.AFTER_SOME_SOLVER_ACTION : squareCompletionType.INITIAL_VALUE_USER);
				grid.stateInvalidated = true;
			} else if (square.hasValue()) {
				this.value = square.getValue();
			} else {
				this.value = "";
			}
		};

		this.input.onfocus = function() {
			this.select();
			addClass(square.possibilitiesDiv, "hidden");
			grid.currentSquare = square;
		};

		this.input.onblur = function() {
			removeClass(square.possibilitiesDiv, "hidden");
			if (grid.currentSquare == square) {
				grid.currentSquare = null;
			}
		};

		this.container.title = "Click to enter value";
	}
	
	Square.prototype = {
		hasValue: function() {
			return grid.state.hasValue(this.row, this.column);
		},
	
		getValue: function() {
			return grid.state.values[this.row][this.column];
		},
		
		setValue: function(value, updateInput, completionType) {
			grid.state.setValue(this.row, this.column, parseInt(value), completionType);
			if (completionType & squareCompletionType.CONDITIONAL_ON_GUESS) {
				this.input.className = "conditionalonguess";
				this.container.title = "Value deduced by solver based on an earlier guess";
			} else {
				switch (completionType) {
					case squareCompletionType.ONLY_SQUARE_FOR_VALUE:
						this.input.className = "solved";
						this.container.title = "Value deduced by solver";
						break;
					case squareCompletionType.ONLY_VALUE_FOR_SQUARE:
						this.input.className = "solved";
						this.container.title = "Value deduced by solver";
						break;
					case squareCompletionType.INITIAL_VALUE_USER:
						this.input.className = "initial";
						this.container.title = "Initial value";
						break;
					case squareCompletionType.INITIAL_VALUE_SAVED:
						this.input.className = "initial";
						this.container.title = "Initial value";
						break;
					case squareCompletionType.AFTER_SOME_SOLVER_ACTION:
						this.input.className = "aftersomesolving";
						this.container.title = "Value added by user after some values were deduced by the solver";
						break;
					case squareCompletionType.GUESSED_VALUE:
						this.input.className = "guessed";
						this.container.title = "Value guessed by solver";
						break;
				}
			}
			if (updateInput) {
				this.input.value = value;
			}
			this.setPossibleValues([value]);
		},
	
		clearValue: function() {
			this.input.value = "";
			this.input.className = "initial";
			this.container.title = "Click to enter value";
			this.setPossibleValues([1, 2, 3, 4, 5, 6, 7, 8, 9]);
			grid.state.removeValue(this.row, this.column);
		},
		
		setPossibleValues: function(possibleValues) {
			this.possibilitiesDiv.innerHTML = possibleValues.join("<wbr />");
		},
	
		highlight: function() {
			addClass(this.container, "highlighted");
		},
	
		unhighlight: function() {
			removeClass(this.container, "highlighted");
		}
	};
	
	/* --------------------------------------------------------------------- */
	
	function Logger(container) {
		this.container = container;
		var lastEntry = null;
		
		function LogEntry(message, state, squareCoords, bold) {
			this.message = message;
			this.state = state;
			this.squareCoords = squareCoords;
			this.bold = bold;
			this.initAsEntry();
			lastEntry = this;
		}

		LogEntry.prototype = {
			initAsEntry: function() {
				this.entryElement = document.createElement("div");
				if (this.bold) {
					this.entryElement.style.fontWeight = "bold";
				}
				this.messageTextNode = document.createTextNode(this.message);
				this.entryElement.appendChild(this.messageTextNode);
				addClass(this.entryElement, "logentry");
		
				var logEntry = this;
				if (this.state) {
					addClass(this.entryElement, "clickable");
					this.entryElement.onclick = function(evt) {
						logEntry.select();
						var e = evt ? evt : window.event;
						stopEventPropagation(e);
					};
				}
			},

			setMessage: function(message) {
				this.messageTextNode.nodeValue = message;
			},

			highlight: function() {
				addClass(this.entryElement, "highlightedentry");
			},

			unhighlight: function() {
				removeClass(this.entryElement, "highlightedentry");
			},

			select: function(scrollIntoView) {
				if (logger.currentEntry) {
					logger.currentEntry.unhighlight();
				}
				if (this instanceof LogNode && !this.expanded) {
					this.expand();
				}
				logger.currentEntry = this;
				if (scrollIntoView && this.entryElement.scrollIntoView) {
					this.entryElement.scrollIntoView();
				}
				this.highlight();
				if (this.state) {
					grid.setState(this.state);
					if (this.squareCoords) {
						if (this.squareCoords[0] instanceof Array) {
							for (var i = 0; i < this.squareCoords.length; i++) {
								grid.squares[this.squareCoords[i][0]][this.squareCoords[i][1]].highlight();
							}
						} else {
							grid.squares[this.squareCoords[0]][this.squareCoords[1]].highlight();
						}
					}
				}
			}
		};

		/* ---------------------------------------------------------------- */

		function LogNode(message, state, squareCoords, initiallyExpanded, element, bold) {
			this.message = message;
			this.state = state;
			this.squareCoords = squareCoords;
			this.bold = bold;
			this.initiallyExpanded = initiallyExpanded;
			this.element = element;
			this.initAsEntry();
			this.initAsNode();
		}
		LogNode.prototype = new LogEntry();
		
		LogNode.prototype.initAsNode = function() {
			var node = this;
			if (typeof this.initiallyExpanded == "undefined") {
				this.initiallyExpanded = true;
			}
			this.expanded = this.initiallyExpanded;
			this.entries = new Array();
			if (this.element) {
				this.entryContainer = this.element;
			} else {
				this.mainContainer = this.entryElement;
				addClass(this.mainContainer, "lognode");
				addClass(this.mainContainer, "success");
				addClass(this.mainContainer, this.initiallyExpanded ? "expanded" : "collapsed");
				
				// Create the +/- expander image
				this.expanderImage = document.createElement("img");
				this.expanderImage.src = this.initiallyExpanded ? collapseImage.src : expandImage.src;
				this.expanderImage.onclick = function(evt) {
					if (node.expanded) {
						node.collapse();
					} else {
						node.expand();
					}
					var e = evt ? evt : window.event;
					stopEventPropagation(e);
				};
				this.expanderImage.title = this.initiallyExpanded ? "Click to collapse" : "Click to expand";
				addClass(this.expanderImage, "clickable");
				this.mainContainer.insertBefore(this.expanderImage, this.messageTextNode);
				
				// Create the container for log entries
				this.entryContainer = document.createElement("div");
				addClass(this.entryContainer, "entrycontainer");
				this.mainContainer.appendChild(this.entryContainer);
			}
		}
		
		LogNode.prototype.expand = function() {
			this.expanded = true;
			if (this.expanderImage) {
				this.expanderImage.src = collapseImage.src;
				this.expanderImage.title = "Click to collapse";
				replaceClass(this.mainContainer, "expanded", "collapsed");
			}
		};
		
		LogNode.prototype.collapse = function() {
			this.expanded = false;
			if (this.expanderImage) {
				this.expanderImage.src = expandImage.src;
				this.expanderImage.title = "Click to expand";
				replaceClass(this.mainContainer, "collapsed", "expanded");
			}
		};
		
		LogNode.prototype.addNode = function(message, state, squareCoords, initiallyExpanded, insertAtStart, bold) {
			var newNode = new LogNode(message, state, squareCoords, initiallyExpanded, null, bold);
			//this.entryContainer.appendChild(newNode.mainContainer);
			if (!this.entryContainer.hasChildNodes() || (logTopDown && !insertAtStart) || (!logTopDown && insertAtStart)) {
				this.entryContainer.appendChild(newNode.mainContainer);
			} else {
				this.entryContainer.insertBefore(newNode.mainContainer, this.entryContainer.firstChild);
			}
			newNode.parent = this;
			this.entries.push(newNode);
			logger.entries.push(newNode);
			return newNode;
		};

		LogNode.prototype.setAsDeadEnd = function() {
			this.collapse();
			this.isDeadEnd = true;
			if (this.mainContainer) {
				replaceClass(this.mainContainer, "fail", "success");
			}
			replaceClass(this.entryContainer, "fail", "success");
		};
		
		LogNode.prototype.log = function(message, state, squareCoords, insertAtStart, bold) {
			var entry = new LogEntry(message, state, squareCoords, bold);
			if (!this.entryContainer.hasChildNodes() || (logTopDown && !insertAtStart) || (!logTopDown && insertAtStart)) {
				this.entryContainer.appendChild(entry.entryElement);
			} else {
				this.entryContainer.insertBefore(entry.entryElement, this.entryContainer.firstChild);
			}
			entry.parent = this;
			this.entries.push(entry);
			logger.entries.push(entry);
			return entry;
		};
		
		LogNode.prototype.clear = function() {
			this.entries.length = 0;
			this.entryContainer.innerHTML = "";
			if (this.mainContainer) {
				this.mainContainer.innerHTML = "";
			}
		};
		
		/* ---------------------------------------------------------------- */
		
		var logTopDown = container.scrollIntoView ? true : false;
		this.entries = new Array();

		var expandImage = new Image();
		expandImage.src = "expand.gif";
		var collapseImage = new Image();
		collapseImage.src = "collapse.gif";

		var logVisible = true;
		this.hide = function() {
			logVisible = false;
			replaceClass(logElement, "hidden", "visible");
		};

		this.show = function() {
			logVisible = true;
			replaceClass(logElement, "visible", "hidden");
			if (lastEntry && lastEntry.entryElement.scrollIntoView) {
				lastEntry.entryElement.scrollIntoView();
			}
		};
		
		this.clear = function() {
			this.rootNode.clear();
			this.entries.length = 0;
			this.currentEntry = null;
			replaceClass(this.container, "success", "fail");
		};

		this.nextEntry = function() {
			if (this.entries.length > 0) {
				var nextEntry;
				if (this.currentEntry) {
					var index = this.entries.getIndex(this.currentEntry);
					if (index < this.entries.length - 1) {
						nextEntry = this.entries[index + 1];
					} else {
						return;
					}
				} else {
					nextEntry = this.entries[0];
				}
				nextEntry.select(true);
			}
		};

		this.previousEntry = function() {
			if (this.entries.length > 0) {
				var previousEntry;
				if (this.currentEntry) {
					var index = this.entries.getIndex(this.currentEntry);
					if (index > 0) {
						previousEntry = this.entries[index - 1];
					} else {
						return;
					}
				} else {
					previousEntry = this.entries[0];
				}
				previousEntry.select(true);
			}
		};

		this.selectFirstEntry = function() {
			/*if (this.entries.length > 0) {
				this.entries[0].select(true);
			}*/
			if (this.firstEntry) {
				this.firstEntry.select(false);
			}
		};

		this.rootNode = new LogNode(null, null, null, true, this.container);
		this.currentEntry = null;
	};
	
	var logger = new Logger(logElement);
	var currentLogNode = logger.rootNode;
	
	function log(message, state, squareCoords, isFirstEntry, insertAtStart, bold) {
		var logEntry = currentLogNode.log(message, state, squareCoords, insertAtStart, bold);
		if (isFirstEntry) {
			logger.firstEntry = logEntry;
		}
	}
	
	/* --------------------------------------------------------------------- */

	function SudokuState(sudokuState) {
		this.init();
		if (typeof sudokuState != "undefined") {
			for (var row = 0; row < sudokuState.values.length; row++) {
				for (var column = 0; column < sudokuState.values[row].length; column++) {
					var value = sudokuState.values[row][column];
					var completionType = sudokuState.completionTypes[row][column];
					this.setValue(row, column, value, completionType);
					this.possibleValues[row][column] = sudokuState.possibleValues[row][column].clone()
				}
			}
		}
	}
	
	SudokuState.prototype = {
		init: function() {
			this.completedSquaresCount = 0;
			
			// Create an internal map of values for each square
			this.values = new Array(9);
			this.completionTypes = new Array(9);
			for (var i = 0; i < this.values.length; i++) {
				this.values[i] = new Array(9);
				this.completionTypes[i] = new Array(9);
			}

			// Set up possible values array for each square
			this.possibleValues = new Array(9);
			for (var row = 0; row < 9; row++) {
				this.possibleValues[row] = new Array(9);
				for (var column = 0; column < 9; column++) {
					this.possibleValues[row][column] = [1, 2, 3, 4, 5, 6, 7, 8, 9];
				}
			}
		},

		hasValue: function(row, column) {
			try {
				return (typeof this.values[row][column] != "undefined");
			} catch (ex) {
				alert("Error: call to hasValue failed. Details: " + ex.message);
			}
		},

		setValue: function(row, column, value, completionType) {
			if (!this.hasValue(row, column)) {
				this.completedSquaresCount++;
			}
			this.values[row][column] = value;
			if (typeof completionType != "undefined") {
				this.completionTypes[row][column] = completionType;
			}
			this.possibleValues[row][column] = [];
		},

		removeValue: function(row, column) {
			if (this.hasValue(row, column)) {
				this.completedSquaresCount--;
				delete this.values[row][column];
			}
		},

		isValueValid: function(row, column, value) {
			return this.possibleValues[row][column].contains(value);
		},

		isCompleted: function() {
			return (this.completedSquaresCount == this.values.length * this.values[0].length);
		},

		actOnAllValues: function(action) {
			for (var row = 0; row < this.values.length; row++) {
				for (var column = 0; column < this.values[row].length; column++) {
					action(row, column, this.values[row][column]);
				}
			}
		},

		actOnAllSetValues: function(action) {
			var state = this;
			this.actOnAllValues(
				function(row, column, value) {
					if (state.hasValue(row, column)) {
						action(row, column, state.values[row][column]);
					}
				}
			);
		},

		toSource: function() {
			var state = this;
			var str = "";
			this.actOnAllValues(
				function(row, column, value) {
					if (state.hasValue(row, column)) {
						str += new String(value);
					} else {
						str += "0";
					}
				}
			);
			return str;
		},

		toState: function() {
			return new SudokuState(this);
		}
	};

	/* --------------------------------------------------------------------- */

	function SudokuSolver() {
		
		// Create reference to this that inner objects can access
		var solver = this;
		
		/* ----------------------------------------------------------------- */
		
		/**
		 * Object encapsulating the current state of the solver, to allow
		 * rollback when solving by force
		 */
		function SudokuSolverState(sudokuSolverState) {
			// If a state is supplied, make the new instance a copy of it
			if (typeof sudokuSolverState != "undefined") {
				for (var i in sudokuSolverState) {
					this[i] = sudokuSolverState[i].clone(true);
				}
			} else {
				// Create a blank state
				this.init(); // Calls SudokuState's init method to initialize the values
	
				function initUniqueValueCollection(uniqueValueCollection) {
					uniqueValueCollection.possibleSquaresForValue = new Array(10); // 0 is not used.
					for (var value = 1; value < uniqueValueCollection.possibleSquaresForValue.length; value++) {
						uniqueValueCollection.possibleSquaresForValue[value] = [0, 1, 2, 3, 4, 5, 6, 7, 8];
					}
					uniqueValueCollection.valuesNotSet = [1, 2, 3, 4, 5, 6, 7, 8, 9];

					uniqueValueCollection.valuesInSameCollection = new Object();
					uniqueValueCollection.valuesInSameCollection[Row.collectionType] = new Array();
					uniqueValueCollection.valuesInSameCollection[Column.collectionType] = new Array();
					uniqueValueCollection.valuesInSameCollection[MiniGrid.collectionType] = new Array();

					uniqueValueCollection.groupsFound = new Array();
				}
				
				// Set up possible squares for values in rows, columns and minigrids
				this.rows = new Array(9);
				this.columns = new Array(9);
				this.miniGrids = new Array(9);
				for (var i = 0; i < 9; i++) {
					this.rows[i] = new Object();
					initUniqueValueCollection(this.rows[i]);
					this.columns[i] = new Object();
					initUniqueValueCollection(this.columns[i]);
					this.miniGrids[i] = new Object();
					initUniqueValueCollection(this.miniGrids[i]);
					this.miniGrids[i].valuesInOneRowOrColumn = new Array();
				}
				this.steps = 0;
			}
		}

		SudokuSolverState.prototype = new SudokuState();
		
		SudokuSolverState.prototype.toSolution = function() {
			if (this.isCompleted()) {
				var solution = this.toState();
				// Remove all references to guesses
				solution.actOnAllValues(
					function(row, column, value) {
						if (solution.completionTypes[row][column] & squareCompletionType.CONDITIONAL_ON_GUESS) {
							solution.completionTypes[row][column] -= squareCompletionType.CONDITIONAL_ON_GUESS;
						} else if (solution.completionTypes[row][column] == squareCompletionType.GUESSED_VALUE) {
							solution.completionTypes[row][column] = squareCompletionType.ONLY_VALUE_FOR_SQUARE;
						}
					}
				);
				solution.steps = this.steps;
				return solution;
			}
			return null;
		};

		/* ----------------------------------------------------------------- */

		function Square(row, column, miniGrid) {
			var square = this;
			this.row = row;
			this.column = column;
			this.miniGrid = miniGrid;
			this.hashCode = "r" + this.row.rowNumber + "c" + this.column.columnNumber;
			
			// Set up listeners arrays
			var valueSetListeners = new Array();
			this.addValueSetListener = function(listenerFunction) {
				valueSetListeners.push(listenerFunction);
			};
	
			var possibleValueRemovedListeners = new Array();
			this.addPossibleValueRemovedListener = function(listenerFunction) {
				possibleValueRemovedListeners.push(listenerFunction);
			};
	
			this.isValueSet = function() {
				return (this.getValue() != null);
			};
			
			this.removePossibleValue = function(value, originalCollection) {
				if (!this.isValueSet()) {
					var possibleValues = this.getPossibleValues();
					possibleValues.remove(value);

					if (possibleValues.length == 1) {
						solver.queueSquare(this, possibleValues[0], squareCompletionType.ONLY_VALUE_FOR_SQUARE, originalCollection, null);
					}
	
					// Alert listeners
					for (var i = 0; i < possibleValueRemovedListeners.length; i++) {
						possibleValueRemovedListeners[i](this, value);
					}
				}
			};
			
			this.setPossibleValues = function(possibleValues) {
				return solver.state.possibleValues[row.rowNumber][column.columnNumber] = possibleValues;
			};

			this.getValue = function() {
				return solver.state.values[row.rowNumber][column.columnNumber];
			};
			
			this.getPossibleValues = function() {
				return solver.state.possibleValues[row.rowNumber][column.columnNumber];
			};
			
			this.setValue = function(value, completionType, originalCollection) {
				if (!this.isValueSet()) {
					solver.state.setValue(this.row.rowNumber, this.column.columnNumber, value, completionType);
					this.setPossibleValues([value]);

					// Log this value being set
					var explanationText;
					var doLog = false;
					
					if (completionType & squareCompletionType.CONDITIONAL_ON_GUESS) {
						completionType = completionType - squareCompletionType.CONDITIONAL_ON_GUESS;
					}
					
					switch (completionType) {
						case squareCompletionType.ONLY_SQUARE_FOR_VALUE:
							doLog = true;
							solver.state.steps++;
							explanationText = "Only remaining possible square that could be " + value + " in " + originalCollection.type;
							break;
						case squareCompletionType.ONLY_VALUE_FOR_SQUARE:
							doLog = true;
							solver.state.steps++;
							explanationText = "Only remaining possible value for square";
							break;
						case squareCompletionType.INITIAL_VALUE_USER:
							explanationText = "Initial value added by user";
							break;
						case squareCompletionType.INITIAL_VALUE_SAVED:
							explanationText = "Initial value from saved puzzle";
							break;
						case squareCompletionType.AFTER_SOME_SOLVER_ACTION:
							doLog = true;
							explanationText = "Value added by user";
							break;
						case squareCompletionType.GUESSED_VALUE:
							doLog = true;
							solver.state.steps++;
							explanationText = "Guessed value";
							break;
						default:
							doLog = true;
							explanationText = "ERROR: completion type is " + completionType;
							break;
					}
					if (doLog) {
						var logMessage = "Square " + this.toString() + " set to " + value + ". Details: " + explanationText;
						log(logMessage, solver.state.toState(), this.getCoords());
					}
						
					// Alert listeners
					for (var i = 0; i < valueSetListeners.length; i++) {
						valueSetListeners[i](this);
					}
					// Ensure this this square is removed from the queue
					solver.removeSquareFromQueue(this);
				}
			};
			
			this.toString = function() {
				return "(" + this.row.getDisplayNumber() + ", " + this.column.getDisplayNumber() + ")";
			};
			
			this.toDisplayString = function() {
				return "(" + (this.row.rowNumber + 1) + ", " + (this.column.columnNumber + 1) + ")";
			};

			this.getCoords = function() {
				return [this.row.rowNumber, this.column.columnNumber];
			};
			
			this.getCollection = function(collectionType) {
				if (collectionType == Row.collectionType) {
					return this.row;
				} else if (collectionType == Column.collectionType) {
					return this.column;
				} else if (collectionType == MiniGrid.collectionType) {
					return this.miniGrid;
				}
				return null;
			};
		}
		
		/* ----------------------------------------------------------------- */

		function UniqueValueCollection() {
		}
		
		UniqueValueCollection.prototype = {
			init: function() {
				this.squares = new Array();
				var collection = this;
				
				this.squareValueSetListener = function(square) {
					var valuesNotSet = collection.getValuesNotSet();
					var possibleSquaresForValue = collection.getPossibleSquaresForValue();
					valuesNotSet.remove(square.getValue());
					possibleSquaresForValue[square.getValue()] = [];
					// Remove current square's value as a possible value from all other squares in the collection
					for (var i = 0; i < collection.squares.length; i++) {
						if (!collection.squares[i].isValueSet()) {
							collection.squares[i].removePossibleValue(square.getValue(), collection);
						}
					}
					// Remove the current square from the list of squares possible for all values
					for (var value = 1; value < possibleSquaresForValue.length; value++) {
						if (valuesNotSet.contains(value)) {
							possibleSquaresForValue[value].remove(collection.getSquareIndex(square));
							if (possibleSquaresForValue[value].length == 1) {
								try {
									solver.queueSquare(collection.squares[possibleSquaresForValue[value][0]], value, squareCompletionType.ONLY_VALUE_FOR_SQUARE, collection);
								} catch (ex) {
									alert(possibleSquaresForValue[value].length);
								}
							}
						}
					}
				};
		
				this.squarePossibleValueRemovedListener = function(square, value) {
					var valuesNotSet = collection.getValuesNotSet();
					var possibleSquaresForValue = collection.getPossibleSquaresForValue();
					// Remove the current square from the list of squares possible for the specified value
					if (valuesNotSet.contains(value)) {
						possibleSquaresForValue[value].remove(collection.getSquareIndex(square));
						if (possibleSquaresForValue[value].length == 1) {
							solver.queueSquare(collection.squares[possibleSquaresForValue[value][0]], value, squareCompletionType.ONLY_SQUARE_FOR_VALUE, collection);
						}
					}
				};
				
				this.checkForPossibilityGroups = function(sizeOfGroup) {
					var doneAnything = false;
					
					var valuesNotSet = this.getValuesNotSet();
					var groups = valuesNotSet.subsets(sizeOfGroup);
	
					// Check each group for squares whose possible values are subsets
					// of the group
					for (var g = 0; g < groups.length; g++) {
						var group = groups[g];
						var doneAnythingWithThisGroup = false;
						var squaresAffectedInGroup = new Array();
						if (!this.isGroupAlreadyFound(group) && !group.equals(valuesNotSet)) {
							var squares = new Array();
							for (var i = 0; i < collection.squares.length; i++) {
								var square = collection.squares[i];
								if (!square.isValueSet() && square.getPossibleValues().isSubsetOf(group)) {
									squares.push(square);
								}
							}
							if (group.length == squares.length) {
								var squareCoords = new Array();
								for (i = 0; i < squares.length; i++) {
									squareCoords.push(squares[i].getCoords());
								}
								log("Found squares with same possible values " + group.join(",") + " in " + this.type, solver.state.toState(), squareCoords);
								this.setGroupFound(group);
								
								// Remove these values from all other squares in the collection
								for (var s = 0; s < collection.squares.length; s++) {
									var square = collection.squares[s];
									if (!square.isValueSet() && !squares.contains(square)) {
										for (var j = 0; j < group.length; j++) {
											if (square.getPossibleValues().contains(group[j])) {
												square.removePossibleValue(group[j], collection);
												doneAnything = true;
												doneAnythingWithThisGroup = true;
												squaresAffectedInGroup.push(square);
											}
										}
									}
								}
								if (doneAnythingWithThisGroup) {
									squareCoords = new Array();
									for (i = 0; i < squaresAffectedInGroup.length; i++) {
										squareCoords.push(squaresAffectedInGroup[i].getCoords());
									}
									log("Removed possible values " + group.join(",") + " from other squares in " + this.type, solver.state.toState(), squareCoords);
									solver.state.steps++;
									return true;
								}
							}
						}
					}
					return doneAnything;
				};

				this.checkForPossibleSquareGroups = function(sizeOfGroup) {
					var doneAnything = false;
					
					var valuesNotSet = this.getValuesNotSet();
					var groups = valuesNotSet.subsets(sizeOfGroup);
	
					// Check each group for squares whose possible values are suupersets
					// of the group
					for (var g = 0; g < groups.length; g++) {
						var group = groups[g];
						var doneAnythingWithThisGroup = false;
						var squaresAffectedInGroup = new Array();
						if (!group.equals(valuesNotSet)) {
							var squares = new Array();
							for (var i = 0; i < collection.squares.length; i++) {
								var square = collection.squares[i];
								if (!square.isValueSet() && square.getPossibleValues().intersects(group)) {
									squares.push(square);
								}
							}
							if (group.length == squares.length) {
								var squareCoords = new Array();
								for (i = 0; i < squares.length; i++) {
									squareCoords.push(squares[i].getCoords());
								}
								log("Found squares that must cover possible values " + group.join(",") + " in " + this.type, solver.state.toState(), squareCoords);
								//this.setGroupFound(group);
								
								// Remove all other values for these squares
								for (var s = 0; s < squares.length; s++) {
									var square = squares[s];
									var possibleValues = square.getPossibleValues().clone(false);
									for (var j = 0; j < possibleValues.length; j++) {
										if (!group.contains(possibleValues[j])) {
											square.removePossibleValue(possibleValues[j], collection);
											doneAnything = true;
											doneAnythingWithThisGroup = true;
											squaresAffectedInGroup.push(square);
										}
									}
								}
								if (doneAnythingWithThisGroup) {
									squareCoords = new Array();
									for (i = 0; i < squaresAffectedInGroup.length; i++) {
										squareCoords.push(squaresAffectedInGroup[i].getCoords());
									}
									log("Removed possible values other than " + group.join(",") + " from these squares in " + this.type, solver.state.toState(), squareCoords);
									solver.state.steps++;
									return true;
								}
							}
						}
					}
					return doneAnything;
				};

				this.checkForPossibleSquaresContainedInOtherCollection = function(collectionType) {
					var valuesNotSet = this.getValuesNotSet();
					var doneAnything = false;
					for (var i = 0; i < valuesNotSet.length; i++) {
						var value = valuesNotSet[i];
						if (!this.getStateObject().valuesInSameCollection[collectionType][value]) {
							var possibleSquares = this.getPossibleSquaresForValue()[value];
							if (possibleSquares.length != 0/* && possibleSquares.length <= 3*/) {
								var inSameCollection = true;
								var lastCollection = null;
								for (var j = 0; j < possibleSquares.length; j++) {
									var square = this.squares[possibleSquares[j]];
									var collection = square.getCollection(collectionType);
									//alert(collection.toSummaryString());
									if (j > 0) {
										inSameCollection = inSameCollection && (collection == lastCollection);
									}
									lastCollection = collection;
								}
							
								if (inSameCollection) {
									var preRemovalState = solver.state.toState();
									var preRemovalSquareCoords = new Array();
									for (var i = 0; i < possibleSquares.length; i++) {
										preRemovalSquareCoords.push(this.squares[possibleSquares[i]].getCoords());
									}
									
									var squares = new Array();
									var removedPossibilityFromSquares = false;
			
									// Remove the current value as a possibility from all other squares in the collection
									for (var j = 0; j < 9; j++) {
										var square = lastCollection.squares[j];
										if (!square.isValueSet() && square.getPossibleValues().contains(value) && !this.squares.contains(square)) {
											square.removePossibleValue(value, this);
											doneAnything = true;
											removedPossibilityFromSquares = true;
											squares.push(square);
										}
									}
									if (removedPossibilityFromSquares) {
										squareCoords = new Array();
										for (var k = 0; k < squares.length; k++) {
											squareCoords.push(squares[k].getCoords());
										}
										log("All possible squares for value " + value + " in " + this.type
											+ " " + this.getDisplayNumber() + " lie in the same " + lastCollection.type, preRemovalState, preRemovalSquareCoords);
										log("Removed possible value " + value + " from other squares in " + lastCollection.type, solver.state.toState(), squareCoords);
										solver.state.steps++;
									}
									this.getStateObject().valuesInSameCollection[collectionType][value] = true;
								}
							}
						}
					}
					return doneAnything;
				};
			},

			getValuesNotSet: function() {
				return this.getStateObject().valuesNotSet;
			},

			getPossibleSquaresForValue: function() {
				return this.getStateObject().possibleSquaresForValue;
			},

			setGroupFound: function(group) {
				this.getStateObject().groupsFound.push(group.join(""));
			},

			isGroupAlreadyFound: function(group) {
				return this.getStateObject().groupsFound.contains(group.join(""));
			},

			getStateObject: function() {},

			getSquareIndex: function(square) {
				return this.squareIndices[square.hashCode];
			},
			
			getDisplayNumber: function() {},

			toSummaryString: function() {
				return this.type + " " + this.getDisplayNumber();
			},

			addSquareToPossibleValues: function(square) {
				var possibleSquaresForValue = this.getPossibleSquaresForValue();
				for (var i = 1; i < possibleSquaresForValue.length; i++) {
					possibleSquaresForValue[i].push(square);
				}
			}
		};
		
		/* ----------------------------------------------------------------- */

		function Row(rowNumber) {
			var row = this;
			this.type = Row.collectionType;
			this.rowNumber = rowNumber;
			this.squareIndices = new Object();
			this.init();
			
			this.addSquare = function(columnNumber, square) {
				this.squares[columnNumber] = square;
				this.addSquareToPossibleValues(square);
				this.squareIndices[square.hashCode] = columnNumber;
				square.addValueSetListener(this.squareValueSetListener);
				square.addPossibleValueRemovedListener(this.squarePossibleValueRemovedListener);
			}
		}
		
		Row.prototype = new UniqueValueCollection();
		Row.prototype.getStateObject = function() {
			return solver.state.rows[this.rowNumber];
		};
		
		Row.prototype.getDisplayNumber = function() {
			return this.rowNumber + 1;
		};

		Row.collectionType = "row";
		
		/* ----------------------------------------------------------------- */

		function Column(columnNumber) {
			var column = this;
			this.type = Column.collectionType;
			this.columnNumber = columnNumber;
			this.squareIndices = new Object();
			this.init();
	
			this.addSquare = function(rowNumber, square) {
				this.squares[rowNumber] = square;
				this.addSquareToPossibleValues(square);
				this.squareIndices[square.hashCode] = rowNumber;
				square.addValueSetListener(this.squareValueSetListener);
				square.addPossibleValueRemovedListener(this.squarePossibleValueRemovedListener);
			}
		}

		Column.prototype = new UniqueValueCollection();
		Column.prototype.getStateObject = function() {
			return solver.state.columns[this.columnNumber];
		};

		Column.prototype.getDisplayNumber = function() {
			return this.columnNumber + 1;
		};

		Column.collectionType = "column";
		
		/* ----------------------------------------------------------------- */

		function MiniGrid(miniGridRowNumber, miniGridColumnNumber) {
			var miniGrid = this;
			this.type = MiniGrid.collectionType;
			this.miniGridRowNumber = miniGridRowNumber;
			this.miniGridColumnNumber = miniGridColumnNumber;
			this.squareIndices = new Object();
			this.init();
	
			// Create mini-grid
			var squareIndex = 0;

			for (var rowNumber = 0; rowNumber < 3; rowNumber++) {
				for (var columnNumber = 0; columnNumber < 3; columnNumber++) {
					var row = solver.rows[3 * miniGridRowNumber + rowNumber];
					var column = solver.columns[3 * miniGridColumnNumber + columnNumber];
					var square = new Square(row, column, this);
	
					this.squares[squareIndex] = square;
					this.squareIndices[square.hashCode] = squareIndex;
					squareIndex++;
					
					square.addValueSetListener(this.squareValueSetListener);
					square.addPossibleValueRemovedListener(this.squarePossibleValueRemovedListener);
	
					// Add the square to its row and column object
					row.addSquare(column.columnNumber, square);
					column.addSquare(row.rowNumber, square);
					this.addSquareToPossibleValues(square);
				}
			};
		}

		MiniGrid.prototype = new UniqueValueCollection();

		MiniGrid.prototype.getStateObject = function() {
			return solver.state.miniGrids[3 * this.miniGridRowNumber + this.miniGridColumnNumber];
		};
		
		MiniGrid.prototype.getDisplayNumber = function() {
			return "(" + (this.miniGridRowNumber + 1) + ", " + (this.miniGridColumnNumber + 1) + ")";
		};

		MiniGrid.collectionType = "mini-grid";
		
		/* ----------------------------------------------------------------- */

		var queuedItems = new Array();
		this.queueSquare = function(square, value, completionType, originalCollection) {
			if (!queuedItems.contains(square)) {
				var queueItem = {
					square: square,
					value: value,
					completionType: completionType,
					originalCollection: originalCollection
				};
				queuedItems.push(queueItem);
			}
		};
		
		this.clearQueue = function() {
			queuedItems = [];
		};
		
		this.removeSquareFromQueue = function(square) {
			for (var i = 0; i < queuedItems.length; i++) {
				if (queuedItems.square == square) {
					queuedItems.remove(queuedItems[i]);
				}
			}
		};
		
		this.squareValueSetListener = function(square) {
			if (solver.isFinished()) {
			}
		};
		
		this.strategy1 = function() {
			// Check mini-grids for possible squares for a value that lie
			// in a single row or column
			log("Checking mini-grids for possible squares for a value that all lie in a single row or column", this.state.toState());
			for (var i = 0; i < this.miniGrids.length; i++) {
				if (this.miniGrids[i].checkForPossibleSquaresContainedInOtherCollection(Row.collectionType)) {
					return true;
				}
				if (this.miniGrids[i].checkForPossibleSquaresContainedInOtherCollection(Column.collectionType)) {
					return true;
				}
			}
			// Check rows for possible squares for a value that in a single mini-grid
			log("Checking rows for possible squares for a value that all lie in a single mini-grid", this.state.toState());
			for (i = 0; i < this.miniGrids.length; i++) {
				if (this.rows[i].checkForPossibleSquaresContainedInOtherCollection(MiniGrid.collectionType)) {
					return true;
				}
			}
			// Check columns for possible squares for a value that in a single mini-grid
			log("Checking columns for possible squares for a value that all lie in a single mini-grid", this.state.toState());
			for (i = 0; i < this.miniGrids.length; i++) {
				if (this.columns[i].checkForPossibleSquaresContainedInOtherCollection(MiniGrid.collectionType)) {
					return true;
				}
			}
			return false;
		};
		
		// Check all collections (rows, columns, mini-grids) for 
		// combinations of squares with the same possible values
		this.strategy2 = function(sizeOfGroup) {
			log("Checking for groups of size " + sizeOfGroup, this.state.toState());
			for (i = 0; i < this.allUniqueValueCollections.length; i++) {
				if (this.allUniqueValueCollections[i].checkForPossibilityGroups(sizeOfGroup)) {
					return true;
				}
			}
			return false;
		};

		// Check all collections (rows, columns, mini-grids) for 
		// squares that cover groups of values
		this.strategy3 = function(sizeOfGroup) {
			log("Checking for squares covering groups of size " + sizeOfGroup, this.state.toState());
			for (i = 0; i < this.allUniqueValueCollections.length; i++) {
				if (this.allUniqueValueCollections[i].checkForPossibleSquareGroups(sizeOfGroup)) {
					return true;
				}
			}
			return false;
		};

		this.solveByForce = function() {
			function solve(initialState) {
				// Find the square for which to guess a value, selecting the square with
				// the fewest possible values.
				var bestSquare = null;
				for (var row = 0; row < 9; row++) {
					for (var column = 0; column < 9; column++) {
						var currentSquare = solver.allSquares[row][column];
						if (!currentSquare.isValueSet() && (bestSquare == null
								|| currentSquare.getPossibleValues().length < bestSquare.getPossibleValues().length)) {
							bestSquare = currentSquare;
						}
					}
				}
				
				// Now go through and try each possible value for the selected square
				var possibleValues = bestSquare.getPossibleValues();
				for (var i = 0; i < possibleValues.length; i++) {
					// Revert to a copy of the initial state
					solver.setSolverState(initialState.clone(true));
					var guessedValue = possibleValues[i];
					bestSquare.setValue(guessedValue, squareCompletionType.GUESSED_VALUE);
					guessing = true;
					var initialLogNode = currentLogNode;
					currentLogNode = currentLogNode.addNode("Guessing value " + guessedValue + " for square " + bestSquare.toString(), solver.state.toState(), bestSquare.getCoords(), true);
					if (solver.applyLogic()) {
						if (solver.isFinished()) {
							// A solution has been found
							var solution = solver.state.toSolution();
							solutions.push(solution);
							log("Found solution in " + solution.steps + " steps", solution);
						} else {
							// In this scenario, some progress has been made and no
							// contradiction has occurred, so solve by force again recursively
							solve(solver.state);
						}
					} else {
						// A contradiction has occurred, so no need to pursue this possibility
						log("CONTRADICTION FOUND");
					}
					currentLogNode = initialLogNode;
					guessing = false;
				}
			}
			log("Solving by force", this.state.toState());
			var solutions = new Array();
			solve(this.state.clone());
			if (solutions.length > 0) {
				if (solutions.length == 1) {
					log("Found 1 solution in " + solutions[0].steps + " steps", solutions[0], null, false, true, true);
				} else {
					var initialLogNode = currentLogNode;
					currentLogNode = currentLogNode.addNode("Found " + solutions.length + " solutions", null, null, false, true, true);
					for (var i = 0 ; i < solutions.length; i++) {
						log("Solution " + (i + 1) + " (" + solutions[i].steps + " steps)", solutions[i]);
					}
					currentLogNode = initialLogNode;
				}
			} else {
				log("No solutions found");
			}
		};
		
		this.hasQueuedItems = function() {
			return queuedItems.length > 0;
		};
		
		// Set values for all queued items and allows recursive solving using simple
		// uniqueness logic. Once this function has been run, more cunning tricks must
		// be employed, after which this function should be run again to mop up
		this.processQueue = function() {
			while (currentItem = queuedItems.shift()) {
				if (!this.state.isValueValid(currentItem.square.row.rowNumber, currentItem.square.column.columnNumber, currentItem.value)) {
					log("INVALID value " + currentItem.value + " for square " + currentItem.square, solver.state.toState(), currentItem.square.getCoords());
					currentLogNode.setAsDeadEnd();
					return false;
				}
				var completionType = guessing ? currentItem.completionType + squareCompletionType.CONDITIONAL_ON_GUESS
					: currentItem.completionType;
				currentItem.square.setValue(currentItem.value, completionType, currentItem.originalCollection);
			}
			return true;
		};

		this.applyLogic = function() {
			var anyProgress = true;
			while (anyProgress && !this.isFinished()) {
				anyProgress = false;
				if (!this.processQueue()) {
					return false;
				} else if (this.isFinished()) {
					return true;
				}
				// Check for groups of 2 or 3 first, since this is what would
				// probably be most evident to the human eye
				anyProgress = anyProgress || this.strategy2(2);
				anyProgress = anyProgress || this.strategy2(3);
				
				// Check for possible squares for a value in a minigrid lying
				// in the same row/column and vice versa
				anyProgress = anyProgress || this.strategy1();
				
				// Check for hidden groups of two or three - these are generally not
				// obvious to the naked eye
				anyProgress = anyProgress || this.strategy3(2);
				anyProgress = anyProgress || this.strategy3(3);
				
				// Check for groups and hidden groups of 4 or more - these are even
				// less obvious to the naked eye
				anyProgress = anyProgress || this.strategy2(4);
				anyProgress = anyProgress || this.strategy3(4);
				anyProgress = anyProgress || this.strategy2(5);
				
				// No need to check any further, since checking for hidden groups of
				// size n is equivalent to checking for groups of size 9-n
			}
			return true;
		};
		
		this.solve = function() {
			logger.hide();
			this.initialState = this.state.toState();
			log("Start positie", this.initialState, null, false, false);
			if (this.applyLogic()) {
				if (!this.isFinished()) {
					this.solveByForce();
				} else {
					var solution = this.state.toSolution();
					log("Found 1 solution in " + this.state.steps + " steps", solution, null, true, true, true);
				}
			} else {
				log("No solutions found");
			}
			logger.show();
		};
		
		this.isFinished = function() {
			return this.state.isCompleted();
		};
		
		this.setSolverState = function(sudokuSolverState) {
			this.state = sudokuSolverState;
			this.clearQueue();
		};
	
		this.setState = function(sudokuState) {
			this.state = new SudokuSolverState();
			this.clearQueue();
			sudokuState.actOnAllSetValues(
				function(row, column, value) {
					solver.rows[row].squares[column].setValue(value, squareCompletionType.INITIAL_VALUE_SAVED);
				}
			);
		};
		
		this.state = new SudokuSolverState();
		
		this.doneAnySolving = false;

		// Create the rows and columns. These squares will be added to these when the
		// mini-grids are created
		this.rows = new Array(9);
		for (var row = 0; row < 9; row++) {
			this.rows[row] = new Row(row);
		}
		
		this.columns = new Array(9);
		for (var column = 0; column < 9; column++) {
			this.columns[column] = new Column(column);
		}
		
		// Create the mini-grids
		this.miniGrids = new Array();
		
		for (var miniGridRowNumber = 0; miniGridRowNumber < 3; miniGridRowNumber++) {
			for (var miniGridColumnNumber = 0; miniGridColumnNumber < 3; miniGridColumnNumber++) {
				this.miniGrids.push(new MiniGrid(miniGridRowNumber, miniGridColumnNumber));
			}
		}
		
		this.allUniqueValueCollections = this.rows.concat(this.columns).concat(this.miniGrids);
		
		this.allSquares = new Array();
		for (var r = 0; r < this.rows.length; r++) {
			this.allSquares[r] = new Array();
			for (var c = 0; c < this.columns.length; c++) {
				var square = this.rows[r].squares[c];
				square.addValueSetListener(this.squareValueSetListener)
				this.allSquares[r][c] = square;
			}
		}

		var guessing = false;
	}
	this.state = new SudokuState();
	this.stateInvalidated = false;
	this.solver = new SudokuSolver();
}

/* ------------------------------------------------------------------------- */

// Extensions to built-in JavaScript objects

Array.prototype.contains = function(val) {
	for (var i = 0; i < this.length; i++) {
		if (this[i] == val) {
			return true;
		}
	}
	return false;
};

Array.prototype.getIndex = function(val) {
	for (var i = 0; i < this.length; i++) {
		if (this[i] == val) {
			return i;
		}
	}
	return -1;
};

Array.prototype.remove = function(val) {
	var index = -1;
	for (var i = 0; i < this.length; i++) {
		if (this[i] == val) {
			index = i;
			break;
		}
	}
	if (index >= 0) {
		this.splice(index, 1);
		return true;
	} else {
		return false;
	}
};

Array.prototype.equals = function(arr) {
	if (this.length == arr.length) {
		for (var i = 0; i < this.length; i++) {
			if (this[i] != arr[i]) {
				return false;
			}
		}
		return true;
	}
	return false;
};

Array.prototype.subsets = function(sizeOfSubset) {
	var subsets = new Array();
	function getSubsets(size, fixedSubsetValues, remainingValues) {
		for (var i = 0; i < remainingValues.length - (size - 1); i++) {
			var newFixedValues = fixedSubsetValues.clone(false);
			newFixedValues.push(remainingValues[i]);
			if (size == 1) {
				subsets.push(newFixedValues);
			} else {
				var newRemainingValues = remainingValues.slice(i + 1);
				getSubsets(size - 1, newFixedValues, newRemainingValues);
			}
		}
	}
	getSubsets(sizeOfSubset, [], this);
	return subsets;
};

Array.prototype.isSubsetOf = function(arr) {
	for (var i = 0; i < this.length; i++) {
		if (!arr.contains(this[i])) {
			return false;
		}
	}
	return true;
};

Array.prototype.intersects = function(arr) {
	for (var i = 0; i < this.length; i++) {
		if (arr.contains(this[i])) {
			return true;
		}
	}
	return false;
};

// The 'recursive' parameter indicates whether to clone just the array
// to contain the same properties or to clone the properties too
Array.prototype.clone = function(recursive) {
	if (recursive) {
		var copy = new Array(this.length);
		for (var i = 0; i < this.length; i++) {
			// This will only work properly for Arrays, Objects and primitives (numbers, strings, booleans)
			if (typeof this[i] != "undefined") {
				if (this[i].clone) {
					copy[i] = this[i].clone(true);
				} else {
					copy[i] = this[i];
				}
			}
		}
		return copy;
	}
	return this.concat([]);
};

Number.prototype.clone = function() { return this.valueOf(); };
String.prototype.clone = function() { return this.valueOf(); };
Boolean.prototype.clone = function() { return this.valueOf(); };
Function.prototype.clone = function() { return this.valueOf(); };


// The 'recursive' parameter indicates whether to clone just the object
// to contain the same properties or to clone the properties too
Object.prototype.clone = function(recursive) {
	var copy = new Object();
	for (var i in this) {
		if (i != "clone") {
			// This will only work properly for Arrays, Objects and primitives (numbers, strings, booleans)
			if (recursive && this[i].clone) {
				copy[i] = this[i].clone(true);
			} else {
				copy[i] = this[i];
			}
		}
	}
	return copy;
};

function stopEventPropagation(evt) {
	if (evt.stopPropagation) {
		evt.stopPropagation();
	} else if (typeof evt.cancelBubble != "undefined") {
		evt.cancelBubble = true;
	}
}

/* ------------------------------------------------------------------------- */

// CSS Utilities

function addClass(el, cssClass) {
	if (!hasClass(cssClass)) {
		if (el.className) {
			el.className += " " + cssClass;
		} else {
			el.className = cssClass;
		}
	}
}

function hasClass(el, cssClass) {
	if (el.className) {
		var classNames = el.className.split(" ");
		return classNames.contains(cssClass);
	}
	return false;
}

function removeClass(el, cssClass) {
	if (hasClass(el, cssClass)) {
		// Rebuild the className property
		var existingClasses = el.className.split(" ");
		var newClasses = new Array()
		for (var i = 0; i < existingClasses.length; i++) {
			if (existingClasses[i] != cssClass) {
				newClasses[newClasses.length] = existingClasses[i];
			}
		}
		el.className = newClasses.join(" ");
	}
}

function replaceClass(el, newCssClass, oldCssClass) {
	removeClass(el, oldCssClass);
	addClass(el, newCssClass);
}