var store = new Table();
function Table(a) {
	//a is optional 9x9 array
	this.it = new Array(9); // (col, row)
	for (var k=0; k<9; k++) {
		this.it[k] = new Array(9);
	}
	if (a) {
		for (var j=0; j<9; j++) {
			for (var i=0; i<9; i++ ) {
				this.it[i][j] = a[i][j];
			}
		}
	}
}
Table.prototype.clone = function() {
	return new Table(this.it);
};
Table.prototype.getDataAt = function(coord) {
	return this.it[coord[0]][coord[1]];
};
Table.prototype.setDataAt = function(coord, value) {
	this.it[coord[0]][coord[1]] = value;
};
Table.prototype.neighbourhoodCol = function(coord) { //iterate down column, so col number is fixed
	//returns a vector of other known numbers in the same column
	var retVect = new Array();
	var temp;
	for (var j=0; j<9; j++ ) {
		temp = this.it[coord[0]][j];
		if (typeof(temp) == "number") {
			retVect.push(temp);
		}
	}
	return retVect;
};
Table.prototype.neighbourhoodRow = function(coord) {
	//returns a vector of other known numbers in the same row
	var retVect = new Array();
	var temp;
	for (var i=0; i<9; i++ ) {
		temp = this.it[i][coord[1]];
		if (typeof(temp) == "number") {
			retVect.push(temp);
		}
	}
	return retVect;
};
Table.prototype.neighbourhoodSquare = function(coord) {
	//returns a vector of known numbers in the same square
	
	//calc top left of square:
	var sqx = (Math.floor(coord[0]/3))*3;
	var sqy = (Math.floor(coord[1]/3))*3;
	
	var retVect = new Array();
	var temp;
	
	//iterate through square
	for (var j=0; j<3; j++) {
		for (var i=0; i<3; i++ ) {
			temp = this.it[sqx+i][sqy+j];
			if (typeof(temp) == "number") {
				retVect.push(temp);
			}
		}
	}
	return retVect;

};

function responseObject(t, r, l) { //constructor
	var clonedTable = t.clone();
	this.obj = { "table":clonedTable, "result":r, "least":l };
}
responseObject.prototype.clone = function() {
	return new responseObject(this.getTable(), this.getResult(), this.getLeastCoords());
}
responseObject.prototype.getTable = function() {
	return this.obj["table"];
};
responseObject.prototype.getResult = function() {
	return this.obj["result"];
};
responseObject.prototype.getLeastCoords = function() {
	return this.obj["least"];
};

function solve() {
	store = getTableData();
	var solution = solveTable(store);
	if (solution.getResult() != "solved") { alert("it appears that this puzzle cannot be solved"); return false; }
	populateForm(solution.getTable());
	return false; //stop action being called
} 
function solveTable(t) { //to be recursed, returns a responseObject
	//alert("recursing...");
	var attempt = findPossibilities(t); //returns a responseObject
	if (attempt.getResult()=="solved") { return attempt.clone(); }
	if (attempt.getResult()=="failed") { return new responseObject(t, "failed", null); }

	var origT = attempt.getTable();
	var coord = attempt.getLeastCoords(); //this is a 2-vector
	var bestAttempt;
	trace("least:"+coord[0]+","+coord[1]);
	var possArray = origT.getDataAt(coord);
	for (var i=0; i<possArray.length; i++ ) { //should have at least 2 entries
		var newT = origT.clone();
		newT.setDataAt(coord, possArray[i]);
		var attempt2 = solveTable(newT);
		if (attempt2.getResult() == "solved") { return attempt2.clone(); }
		if (attempt2.getResult() == "unsolved") { bestAttempt = attempt2.clone(); } //not really best, just an attempt that didn't fail
	}
	if (bestAttempt) { return bestAttempt.clone(); }
	else { 
		return new responseObject(origT, "failed", null); 
	}

}

function findPossibilities(inTable) { 
	var outTable = inTable.clone(); // we work in place, so make clone of original to work on
	var coord = new Array(2);
	var response = "solved";
	var least;
	var leastLength = 10;
	for (var j=0; j<9; j++) {
		for (var i=0; i<9; i++ ) {
			coord = [i, j]; //col, row
			if (typeof(outTable.getDataAt(coord)) == "number") {
							continue; } // already filled in
			var nr = outTable.neighbourhoodRow(coord);
			var nc = outTable.neighbourhoodCol(coord);
			var ns = outTable.neighbourhoodSquare(coord);
			var nu = union(nr, union(nc, ns)); //all known numbers it can't be
			if (nu.length==9) { // gone wrong
				response="failed";
				break;
			}
			var un = makeNegative(nu);
			if (un.length==1) { // found entry, stored as a number
				outTable.setDataAt(coord, un[0]);
			} else {
				outTable.setDataAt(coord, un); // otherwise store array of possibilities
				response = "unsolved";
				if (un.length < leastLength) {
					leastLength = un.length;
					least = coord;
				}
			}
		}
			//showTable(outTable);
		if (response=="failed") break;
	} 
	return new responseObject(outTable, response, least);
}
function union(a, b) { //arrays
	if (!b || b.length==0) return a;
	if (!a || a.length==0) return b;
	var retVect = new Array();
	for (var i=0; i<a.length; i++) {
		retVect.push(a[i]);
	} //deep copy of a
	var tester;
	var gotIt;
	for (var i=0; i<b.length; i++) {
		tester = b[i];
		gotIt = false;
		for (var j=0; j<a.length; j++) {
			if (a[j] == tester) {
				gotIt = true;
				break;
			}
		}
		if (gotIt) continue;
		retVect.push(tester);
	}
	return retVect;
}
function makeNegative(v) {
	var set = [1, 2, 3, 4, 5, 6, 7, 8, 9 ];
	for (var i=0; i<v.length; i++) {
		set[v[i]-1] = null; // put null in place of found number
	}
	var retVect= new Array();
	for (var i=0; i<9; i++) { // accumulate non-null entries
		if (set[i]) { retVect.push(set[i]); }
	}
	return retVect;
}
function getTableData() {
	var t = new Table();
	var inputObj;
	var next;
	for (var j=0; j<9; j++) {
		for (var i=0; i<9; i++ ) {
			inputObj = document.getElementById("a"+i+"_"+j);
			next = inputObj.value;
			if (next!="") {
				t.setDataAt([i,j], Number(next));
			}
		}
		
	}
	//showTable(t);
	return t;
}
function populateForm(t) {
	var inputObj;
	var next;
	var temp;
	for (var j=0; j<9; j++) {
		for (var i=0; i<9; i++ ) {
			inputObj = document.getElementById("a"+i+"_"+j);
			temp = t.getDataAt([i,j])
			inputObj.value = (temp) ? temp : "";
		}
	}
	
}
function showTable(t) {
	var temp;
		for (var j=0; j<9; j++) {
	var g = "";
		for (var i=0; i<9; i++ ) {
			temp = t.getDataAt([i,j]);
			g+=((temp) ? temp : ".")+" ";
		}
		
		trace("<pre>"+g+"</pre>");
		}
}
function trace(s) {
	return;
	var tr = document.getElementById("trace");
	var para = document.createElement("p");
	tr.appendChild(para);
	para.innerHTML=s;
}
function resetTable() {
	populateForm(store);
}
function clearTable() {
	populateForm(new Table([[null,null,null,null,null,null,null,null,null],
						   [null,null,null,null,null,null,null,null,null],
						   [null,null,null,null,null,null,null,null,null],
						   [null,null,null,null,null,null,null,null,null],
						   [null,null,null,null,null,null,null,null,null],
						   [null,null,null,null,null,null,null,null,null],
						   [null,null,null,null,null,null,null,null,null],
						   [null,null,null,null,null,null,null,null,null],
						   [null,null,null,null,null,null,null,null,null]]));
}