function shuffle(arr) {
	//+ Jonas Raoni Soares Silva
	//@ http://jsfromhell.com/array/shuffle [rev. #1]
	for(var j, x, i = arr.length; i; j = parseInt(Math.random() * i), x = arr[--i], arr[i] = arr[j], arr[j] = x);
	return arr;
}
function choice(arr) {
	return arr[Math.floor(Math.random()*arr.length)]
}
Array.prototype.index =  function(v) {
	for(var i = 0; i < this.length; i++) {
		if(this[i] == v) return i;
	}
	return false;
}
Array.prototype.contains =  function(v) {
	return this.index(v) !== false;
}

function getValidValues(r, c) {
	if(r < 0 || r > 8 || c < 0 || c > 8) {
		alert("Bad call to getValidVals("+r+","+c+")")
		return
	}
	vals = new Array(1,2,3,4,5,6,7,8,9);
	for(var i = 0; i < 9; i++) {
		if(i != c && board[r][i] != null) {
			idx = vals.index(board[r][i])
			if(idx !== false) vals.splice(idx,1)
		}
		if(i != r && board[i][c] != null) {
			idx = vals.index(board[i][c])
			if(idx !== false) vals.splice(idx,1)
		}
	}
	for(var r2 = Math.floor(r/3)*3; r2 < Math.floor(r/3)*3+3; r2++) {
		for(var c2 = Math.floor(c/3)*3;c2 < Math.floor(c/3)*3+3; c2++) {
			if(r2 == r && c2 == c) continue
			if(board[r2][c2] != null) {
				idx = vals.index(board[r2][c2])
				if(idx !== false) vals.splice(idx,1)
			}
		}
	}
	return vals
}

function createBoard() {
	board = new Array(9)
	for(var i = 0; i < 9; i++) {
		board[i] = new Array(9)
	}
	var r = 0
	var chval
	var valid_vals = new Array(9)
	var board_resets = 0
	var loopProtection = 0
	while(r < 9) {
		loopProtection++
		if(loopProtection > 180) {
			alert("Please try reloading. It seems that I've gone into an infinite loop.");
			return;
		}
		chval = false
		var nextRow = true
		// If all values are filled, go to next row.
		for(var i = 0; i < board[r].length; i++)
			if(board[r][i] == null) {
				nextRow = false
				break
			}
		if(nextRow) r++
		if(r >= 9) continue;
		// Find valid values.
		for(var i = 0; i < 9; i++) {
			if(board[r][i] != null) {
				valid_vals[i] = null
				continue
			} else {
				valid_vals[i] = getValidValues(r,i)
			}
			// If the field only has 1 valid value:
			if(valid_vals[i].length == 0) {
				// We can't fill the values because the column, rows, and
				// squares have a collision preventing continuing the fill.
				// There may be a better solution here. Possibly fill out
				// the full board (or possibly 3x3 squares) instead of
				// rows at a time.
				board_resets += 1
				if(board_resets > 3) {
					// If it resets too many times, just start a new board.
					board_resets = 0
					for(var j = 0; j < 9; j++)
						for(var k = 0; k < 9; k++)
							board[j][k] = null
				} else {
					for(var r2 = Math.floor(r/3)*3; r2 < Math.floor(r/3)*3+3; r2++)
						board[r2] = new Array(9)
				}
				valid_vals = new Array(9)
				r = Math.floor(r/3)*3
				chval = true
				break
			}
			if(valid_vals[i].length == 1) {
				board[r][i] = valid_vals[i][0]
				chval = true
				break
			}
		}
		if(chval == true) continue
		// Detect if one value is only valid in one field
		var counts = new Array(9);
		for(var i = 0; i < valid_vals.length; i++) {
			if(valid_vals[i] == null) continue
			for(var j = 0; j < valid_vals[i].length; j++) {
				if(counts[valid_vals[i][j]] != null)
					counts[valid_vals[i][j]] += 1
				else
					counts[valid_vals[i][j]] = 1
			}
		}
		for(var i = 0; i < counts.length; i++) {
			if(counts[i] == 1)
				for(var j = 0; j < valid_vals.length; j++) {
					if(valid_vals[j] == null) continue
					if(valid_vals[j].contains(i)) {
						board[r][j] = i
						chval = true
						break
					}
				}
		}
		if(chval == true) continue
		var ropts = new Array()
		for(var i = 0; i < valid_vals.length; i++) {
			if(valid_vals[i] == null) continue
			if(valid_vals[i].length == 0) {
				alert("Should not happen.")
				return
			} else if(board[r][i] == null) {
				ropts[ropts.length] = i
			}
		}
		var col = -1
		col = choice(ropts)
		board[r][col] = choice(valid_vals[col])
	}
	filterOut()
}

DIFF_HARD = 74
DIFF_MED = 68
DIFF_EASY = 62

function filterOut() {
	var removed = 0
	var misses = 0
	
	var removedVals = new Array()
	
	var avail = new Array();
	for(var i = 0; i < 81; i++) {
		var c = i%9, r = Math.floor(i/9)
		if(board[r][c] != null)
			avail[avail.length] = new Array(Math.floor(i/9), i%9)
	}
	shuffle(avail)
	shuffle(avail)
	
	var idx = 0
	var rmvSkip = 0
	while(removed + misses/1600 < DIFF_MED) {
		if(Math.random() < .5 && removed < 48 && removedVals.length > removed/14-rmvSkip/15 && !removedVals.contains(board[avail[idx][0],avail[idx][1]])) {
			// Remove numbers consistently most of the time
			rmvSkip++
			idx++
		} else {
			validVals = getValidValues(avail[idx][0], avail[idx][1])
			if(validVals.length == 1) {
				if(!removedVals.contains(board[avail[idx][0]][avail[idx][1]]))
					removedVals[removedVals.length] = board[avail[idx][0]][avail[idx][1]]
				board[avail[idx][0]][avail[idx][1]] = null
				removed++
				avail.splice(idx,1)
				//idx = 0
				if(misses > 400) alert("hit after 400")
			} else {
				if(validVals >= 4)
					avail.splice(idx,1)
				idx = (idx+1) % avail.length
				misses++
			}
		}
		if(idx = 0) {
			shuffle(availVals)
		}
	}
}