function Grid() {
	this.cells = new Array();
	for (var i = 0; i < gridsize; i++)
		this.cells[i] = 0;
}

Grid.prototype.clone = function Clone() {
	var newGrid = new Grid();
	for (var i = 0; i < gridsize; i++)
		newGrid.cells[i] = this.cells[i];
	return newGrid;
}

function CountConstraints(val) {
	var cc = 0;
	for (var i = 1; i <= dim; i++)
		if (((1 << i) & val) != 0)
			cc++;
	return cc;
}

Grid.prototype.mostConstrained = function MostConstrained() {
	var max = -1;
	var maxp = -1;
	for (var i = 0; i < gridsize; i++) {
		if ((this.cells[i] & 1) == 0) {
			v = CountConstraints(this.cells[i]);
			if (v >= max) {
				max = v;
				maxp = i;
			}
		}
	}
	return maxp;
}


function AllOptions(val) {
	var cc = new Array;
	var n = 0;
	for (var i = 1; i <= dim; i++)
		if (((1 << i) & val) == 0) 
			cc[n++] = i;
	return cc;
}

function CellText(d) {
	if (d & 1) {
		for (var i = 1; i <= dim; i++)
			if ((d | (1 << i)) == 1023) 
				return "" + i;
		return "_";
	}
	else 
		return "?" + AllOptions(d);
}

Grid.prototype.setDigit = function SetDigit(pos, digit) {
	var r = Math.floor(pos / dim);
	var c = pos % dim;
	var br = Math.floor(r / subunit) * subunit;
	var bc = Math.floor(c / subunit) * subunit;
	var bit_value = (1 << digit);
	for (var i = 0; i < dim; i++) {
		this.cells[i + r * dim] |= bit_value;
		this.cells[c + i * dim] |= bit_value;
		this.cells[bc + (i % subunit) + (br + Math.floor(i / subunit)) * dim] |= bit_value;
	}
	this.cells[pos] = 1023 - (1 << digit);
}

function solve(startString) {
	var workGrid = new Grid();
	solutionCount = 0;
	for (var i = 0; i <= gridsize; i++) {
		var digit = parseInt(startString.substr(i, 1));
		if (digit >= 1 && digit <= dim)
			workGrid.setDigit(i, digit);
	}
	workGrid.searchSolutions();
//	if (solutionCount==1) 
//		alert("Eine Lösung");
//	else if (solutionCount > 1) 
//		alert("Mehrere Lösungen");
//	else
//		alert("Keine Lösung");

	var solutionString = "";
	for (var i = 0; i < gridsize; i++) {
		solutionString += CellText(grid.cells[i]);
	}
	return solutionString;
}


Grid.prototype.searchSolutions = function SearchSolutions() {
	while (this.isOK()) {
		if (this.isSolved()) {
			solutionCount++;
			if (1 < solutionCount) 
				return this;
			grid = this.clone();
			return null;
		}
		var p = this.mostConstrained();
		if (p < 0)
			return null;
		var l = AllOptions(this.cells[p]);
		if (l.length < 1)
			return null;
		for (var i = 1; i < l.length; i++) {
			var tmpGrid = this.clone();
			tmpGrid.setDigit(p, l[i]);
			tmpGrid = tmpGrid.searchSolutions();
			if (tmpGrid)
				return tmpGrid;
		}
		this.setDigit(p, l[0]);
	}
	return null;
}

Grid.prototype.isOK = function IsOK() {
	for (var i = 0; i < gridsize; i++) {
		if ((this.cells[i] & 1022) == 1022) 
			return false;
	}
	return true;
}

Grid.prototype.isSolved = function IsSolved() {
	for (var i = 0; i < gridsize; i++) {
		if ((this.cells[i] & 1) == 0)
			return false;
	}
	return true;
}

var grid = new Grid();
var solutionCount;
var dim = 9;
var gridsize = 81;
var subunit = 3;