// copied from http://lsrfire.ath.cx/~lsr/js/sudoku.html with permission
//////////////////////////////////////
/*
 * Copyright (C) 2006 Rene Scharfe
 *
 * sudoku.js - a Sudoku solver that tries not to use brute force
 *
 */
function Board() {
	this.clear = function () {
		for (var i = 0; i < 81; i++) {
			values[i] = 0;
			possibilities[i] = allPossibilities;
			possibilityCounts[i] = 9;
		}
	};

	this.setValue = function (index, value) {
		if (values[index] != 0)
			return 0;
		var changed = possibilityCounts[index];
		values[index] = value;
		possibilities[index] = 0;
		possibilityCounts[index] = 0;
		var box = this.find(index, boxes);
		var column = this.find(index, columns);
		var row = this.find(index, rows);
		for (var i = 1; i <= 9; i++) {
			changed += this.removePossibility(boxes[box][i], value);
			changed += this.removePossibility(columns[column][i], value);
			changed += this.removePossibility(rows[row][i], value);
		}
		return changed;
	};
	this.removePossibility = function (index, value) {
		var before = possibilities[index];
		possibilities[index] &= ~possibilityValues[value];
		if (possibilities[index] == before)
			return 0;
		possibilityCounts[index] = possibilityCounts[index] - 1;
		return 1;
	};
	this.getPossibilities = function (index) {
		var a = new Array();
		for (var i = 1, n = possibilityCounts[index]; i <= 9, n > 0; i++) {
			if (this.isPossible(index, i)) {
				n = n - 1;
				a[a.length] = i;
			}
		}
		return a;
	};
	this.isPossible = function (index, value) {
		return (possibilities[index] & possibilityValues[value]) != 0;
	};
	
	this.readBoard = function (sudoku81String) {
		this.clear();
		for (var row = 0;  row < 9; row++) {
			for (var column = 0; column < 9; column++) {
				var index = rows[row + 1][column + 1];
				var value = sudoku81String.substr(row * 9 + column, 1);
				if (1 <= value && value <= 9) {
					this.setValue(index, value);
				}
			}
		}
	};

	this.setState = function (myValues, myPossibilities, myPossibilityCounts) {
		for (var i = 0; i < 81; i++) {
			values[i] = myValues[i];
			possibilities[i] = myPossibilities[i];
			possibilityCounts[i] = myPossibilityCounts[i];
		}
	};
	this.check = function () {
		for (var i = 0; i < 81; i++) {
			if (possibilityCounts[i] == 0 && values[i] == 0)
				return 1;
		}
		return 0;
	};
	this.guess = function (index, value) {
		var testdummy = new Board();
		testdummy.setState(values, possibilities, possibilityCounts);
		testdummy.setValue(index, value);
		while (testdummy.think(1));
		return testdummy.check();
	};

	this.think = function (n) {
		flags = n;
		var removed = 0;
		for (var i = 0; i < 81; i++) {
			if (possibilityCounts[i] == 1) {
				var value = this.getPossibilities(i)[0];
				removed += this.setValue(i, value);
			}
		}
		if (!removed && flags & 1) {
			for (var i = 1; i <= 9; i++) {
				removed += this.findLonelyPossibility(boxes[i]);
				removed += this.findLonelyPossibility(columns[i]);
				removed += this.findLonelyPossibility(rows[i]);
			}
			if (removed)
				used |= 1;
		}
		if (!removed && flags & 2) {
			for (var i = 1; i <= 9; i++) {
				removed += this.findConstraints(boxes[i]);
				removed += this.findConstraints(columns[i]);
				removed += this.findConstraints(rows[i]);
			}
			if (removed)
				used |= 2;
		}
		if (!removed && flags & 8) {
			for (var i = 0; i < 81; i++) {
				if (possibilityCounts[i] == 2) {
					var p = this.getPossibilities(i);
					var a = this.guess(i, p[0]);
					var b = this.guess(i, p[1]);
					var impossible = 0;
					if (a == 0 && b == 1)
						impossible = p[1];
					if (a == 1 && b == 0)
						impossible = p[0];
					if (impossible)
						removed += this.removePossibility(i, impossible);
					break;
				}
			}
			if (removed)
			{
				used |= 8;
			}
		}
		return removed;
	};

	this.findLonelyPossibility = function (a) {
		var removed = 0;
		for (var value = 1; value <= 9; value++) {
			var n = 0;
			var index;
			for (var i = 1; i <= 9; i++) {
				if (this.isPossible(a[i], value)) {	
					n++;
					index = a[i];
				}
			}
			if (n == 1) {
				removed += this.setValue(index, value);
			}
		}
		return removed;
	};

	this.crossSection2 = function (value, i1, i2) {
		if (flags & 4 == 0)
			return 0;
		var removed = 0;
		var c1 = this.find(i1, columns);
		var r1 = this.find(i1, rows);
		var b1 = this.find(i1, boxes);
		var c2 = this.find(i2, columns);
		var r2 = this.find(i2, rows);
		var b2 = this.find(i2, boxes);
		var ce = (c1 == c2);
		var re = (r1 == r2);
		var be = (b1 == b2);
		if (ce && be) {
			var column = columns[c1];
			var box = boxes[b1];
			for (var i = 1; i <= 9; i++) {
				if (column[i] != i1 && column[i] != i2) {
					removed += this.removePossibility(column[i], value);
				}
				if (box[i] != i1 && box[i] != i2) {
					removed += this.removePossibility(box[i], value);
				}
			}
		}
		if (re && be) {
			var row = rows[r1];
			var box = boxes[b1];
			for (var i = 1; i <= 9; i++) {
				if (row[i] != i1 && row[i] != i2) {
					removed += this.removePossibility(row[i], value);
				}
				if (box[i] != i1 && box[i] != i2) {
					removed += this.removePossibility(box[i], value);
				}
			}
		}
		if (removed)
			used |= 4;
		return removed;
	};
	this.crossSection3 = function (value, i1, i2, i3) {
		if (flags & 4 == 0)
			return 0;
		var removed = 0;
		var c1 = this.find(i1, columns);
		var r1 = this.find(i1, rows);
		var b1 = this.find(i1, boxes);
		var c2 = this.find(i2, columns);
		var r2 = this.find(i2, rows);
		var b2 = this.find(i2, boxes);
		var c3 = this.find(i3, columns);
		var r3 = this.find(i3, rows);
		var b3 = this.find(i3, boxes);
		var ce = (c1 == c2 && c1 == c3);
		var re = (r1 == r2 && r1 == r3);
		var be = (b1 == b2 && b1 == b3);
		if (ce && be) {
			var column = columns[c1];
			var box = boxes[b1];
			for (var i = 1; i <= 9; i++) {
				if (column[i] != i1 && column[i] != i2 && column[i] != i3) {
					removed += this.removePossibility(column[i], value);
				}
				if (box[i] != i1 && box[i] != i2 && box[i] != i3) {
					removed += this.removePossibility(box[i], value);
				}
			}
		}
		if (re && be) {
			var row = rows[r1];
			var box = boxes[b1];
			for (var i = 1; i <= 9; i++) {
				if (row[i] != i1 && row[i] != i2 && row[i] != i3) {
					removed += this.removePossibility(row[i], value);
				}
				if (box[i] != i1 && box[i] != i2 && box[i] != i3) {
					removed += this.removePossibility(box[i], value);
				}
			}
		}
		if (removed)
			used |= 4;
		return removed;
	};
	this.findConstraints = function (a) {
		var removed = 0;

		/* index: cell value (1..9), value: string of indices in a where the cell value is possible */
		var s = new Array();
		for (var value = 1; value <= 9; value++) {
			s[value] = "";
			for (var i = 1; i <= 9; i++) {
				if (this.isPossible(a[i], value)) {
					s[value] += "" + i;
				}
			}
		}

		/* index: string of indices in a (an area), value: string of values that are possible within this area */
		var positions = new Array();
		for (var value = 1; value <= 9; value++) {
			var position = s[value];
			if (position.length == 0)
				continue;
			if (position.length == 2) {
				var c1 = position.charAt(0);
				var c2 = position.charAt(1);
				removed += this.crossSection2(value, a[c1], a[c2]);
			}
			if (position.length == 3) {
				var c1 = position.charAt(0);
				var c2 = position.charAt(1);
				var c3 = position.charAt(2);
				removed += this.crossSection3(value, a[c1], a[c2], a[c3]);
			}
			if (positions[position]) {
				positions[position] += "" + value;
			} else {
				positions[position] = "" + value;
			}
		}

		for (var position in positions) {
			/* take subsets into account */
			for (var p in positions) {
				if (!this.isTrueSubset(position, p))
					continue;
				for (var i = 0; i < positions[p].length; i++) {
					var c = positions[p].charAt(i);
					if (positions[position].indexOf(c) == -1) {
						positions[position] += "" + c;
					}
				}
			}

			/*
			 * if the number of possible values and the size of the area are equal,
			 * then no other value can occur within the are
			 */
			if (position.length == positions[position].length) {
				var inverse = new Array();
				for (var i = 1; i <= 9; i++) {
					if (positions[position].indexOf(i) == -1) {
						inverse[inverse.length] = i;
					}
				}
				for (var p = 0; p < position.length; p++) {
					var index = a[position.charAt(p)];
					for (var i in inverse) {
						removed += this.removePossibility(index, inverse[i]);
					}
				}
			}
		}
		return removed;
	};
	this.isTrueSubset = function (set, subset) {
		if (set.length <= subset.length)
			return false;
		for (var i = 0; i <= subset.length; i++) {
			var c = subset.charAt(i);
			if (set.indexOf(c) == -1)
				return false;
		}
		return true;
	};

	this.find = function (index, a) {
		for (var i = 1; i <= 9; i++) {
			for (var j = 1; j <= 9; j++) {
				if (a[i][j] == index) {
					return i;
				}
			}
		}
		return 0;
	};

	this.solve = function (n, sudoku81String) {
		flags = n;
		this.readBoard(sudoku81String);
		while (this.think(flags));
		return used;
	};

	possibilityValues = new Array();
	allPossibilities = 0;
	for (var i = 1, n = 1; i <= 9; i++, n *= 2) {
		possibilityValues[i] = n;
		allPossibilities += n;
	}

	var flags = 0;
	var used = 0;
	var values = new Array();
	var possibilities = new Array();
	var possibilityCounts = new Array();
	var columns = new Array();
	var rows = new Array();
	var boxes = new Array();
	for (var i = 1; i <= 9; i++) {
		columns[i] = new Array();
		rows[i] = new Array();
		boxes[i] = new Array();
	}
	for (var row = 0; row < 9; row++) {
		for (var column = 0; column < 9; column++) {
			boxes[Math.floor(column / 3) + Math.floor(row / 3) * 3 + 1][(column % 3) + (row % 3) * 3 + 1] =
			columns[column + 1][row + 1] =
			rows[row + 1][column + 1] = row * 9 + column;
		}
	}
}
// TEST: <input type="submit" accesskey="Z" onclick="alert(new Board().solve(15,'602000000000008905090640010004760030000000000060031700070093080901400000000000603')); return false;" value="lösen" /> 
document.write("<div style='display:none;' accesskey='P' id='getDifficulty' onclick=\"var diff = new Board().solve(15,getSudokuNumber(SudokuDaten)) + ''; alert(diff); return false;\" ></div>");