<!--
var HTML =
		'<style type="text/css">'
	+	'.Link { color:blue; font-weight: bold; text-decoration: underline; cursor:pointer; cursor:hand; }'
	+	'</style>'
  + '<div style="float:left;">'
  +  '<form name="game" method="post" action="http://zfacts.com/p/582.html">'
    +  '<span id="board">x</span>'
  +	'</form>'
  + '</div>'
+  '<div id="buttons" style="float:left; margin-left:10px;">'
 +  '<span style="background-color:#CC9;">&nbsp;<span class="Link" onclick="javascript:solve()">Solve</span>&nbsp;</span><br><br>'
 +  '<span style="background-color:#CC9;">&nbsp;<span class="Link" onclick="javascript:check()">Check</span>&nbsp;</span><br><br>'
 +  '<span style="background-color:#CC9;">&nbsp;<span class="Link" onclick=\'javascript:clearX("all")\'>Clear All</span>&nbsp;</span><br><br>'
 +  '<span style="background-color:#CC9;">&nbsp;<span class="Link" onclick=\'javascript:clearX("machine")\'>Clear Solution</span>&nbsp;</span>'
+  '</div>'
+  '<div style="float:left; border:1px solid black; width:200px; height:100px; text-align:center;">'
 +  '<span id="count";></span><br>'
 +  '<span id="mess";></span><br>'
+  '</div>';
document.getElementById('sudoku').innerHTML = HTML;

var n = 3; var n2 = n*n; var n22 = n2*n2;
var count=0;
var Rx, Cx;					// coordinates of conflicting cell from Bok (when not ok).
var B  = new Array(n2);		for (i=0; i <n2; i++) B[i]=new Array(n2);		// Board contains 0=>Blank, or {1|2|...9} (for n=3)
var M  = new Array(n2);		for (i=0; i <n2; i++) M[i]=new Array(n2);		// Map contains 0=>set by program, 1=>set by player
var NR = new Array(n2);		for (i=0; i <n2; i++) NR[i]=new Array(n2);	// [Number (1--9)],[row] => 1 if taken, => 0 if not.
var NC = new Array(n2);		for (i=0; i <n2; i++) NC[i]=new Array(n2);	// Same Column info for all values
var NB = new Array(n2);		for (i=0; i <n2; i++) NB[i]=new Array(n2);	// Same block info for all values
// var WR = new Array(n22), WC = new Array(n22), WB = new Array(n22);		// WR[27] tells which row cell 27 is in.
var WV = new Array(n22), WVR = new Array(n22);		// WV[27] tells value we are on , 0-8=>1, 9-17=>2
var WVB = new Array(n2);	for (i=0; i <n2; i++) WVB[i]=new Array(n2);	// Same block info for all values
var slow = 0;
function clearNW() {
	w = 0;
	for (var r=0; r<n2; r++) {	for (var c=0; c<n2; c++) {
			NR[r][c]=NC[r][c]=NB[r][c]=0;
		//	WR[w] = r;	WC[w] = c;	WB[w] = 
			WV[w] = r; WVR[w] = c;	WVB[r][c] = 3*Math.floor(r/n) + Math.floor(c/n);	// row, column and block number
						// as w {0 --> 81} place values WV[w] in row WVR[w]. Val 1 in Rows 0--8, then Val 2 in ...
			w += 1;		// 
	}	}
}
setUp();
function setUp() {		// SetUp Board only used at very beginning
	var board="", ID;
	clearBM('all');
	for (var r=0; r<n2; r++) {
		for (var c=0; c<n2; c++) {
			ID = 'x'+r+c;
			board += '<input id="' +ID+ '" style="font-weight:bold; text-align:center;" type="text" value="" size="2" maxlength="1">';
			if (c%n==n-1) board += '&nbsp;&nbsp;';
		}	board += '<br>';
		if (r%n==n-1) board += '<br>';
	}
	var tag = document.getElementById('board'); 
	tag.innerHTML = board;
	setPuzzle();
	clearX('machine');
}
function solve() {
	clearNW();
	var ok;	
	count = 0;
	var t1 = new Date().getTime();
	clearX('machine')
	check ();	
	fastSet(); 
	
	ok = faster(-1);
	if (!ok) message('mess','Impossible');
	var t2 = new Date().getTime();
	writeBoard();
	message('count', count+' legal moves tried.<br>'+ (t2-t1)+ ' thousandths of a second.');
}
function fastSet() {	// This records the problem information
	var r,c,b,v;
	var p = new Array(0,0,0,0,0,0,0,0,0); 	// popularity of values in the problem
	for (var r=0; r<n2; r++) {
		for (var c=0; c<n2; c++) {
			if (M[r][c]==1) {
				v = B[r][c]-1;
				b = WVB[r][c];
				NR[v][r] = NC[v][c] = NB[v][b] = 1;
				p[v] += 1;
			}
		}
	}
/*	for (w=0; w<n22; w++) {
		r = WR[w]; c = WC[w]; b = WB[w];
		if (M[r][c]==1) {
			v = B[r][c]-1;
			NR[v][r] = NC[v][c] = NB[v][b] = 1;
			p[v] += 1;
		}
	}*/
	var z = new Array(0,1,2,3,4,5,6,7,8);
	var t;
	for (j=0; j<8; j++)
	{	for (i=0; i<8; i++)
		{	if (p[i]<p[i+1])
			{	t = p[i]; p[i]=p[i+1]; p[i+1]=t;
				t = z[i]; z[i]=z[i+1]; z[i+1]=t;
			}
		}
	}
	for (i=0; i<n22; i++) WV[i] = z[WV[i]];
}
function faster(w) {						// 
	var v, r, c, b;
	do {
		w += 1; if (w==n22) return 1;
		v = WV[w]; r = WVR[w];
	}
	while (NR[v][r]);
	for (c=0; c<9; c++) {
		if ( M[r][c] ) continue;								// cell is full
		b = WVB[r][c];
		if ( ! (NR[v][r] || NC[v][c] || NB[v][b]) ) {				// Test possible value at w
			count++;					//		if (slow)	document.getElementById('x'+r+c).value = v+1;
			M[r][c] = 2;	NR[v][r] = NC[v][c] = NB[v][b] = 1;
			if ( faster(w)  ) { B[r][c] = v+1; return 1;} 		// Test if more progress is possible.
			else	M[r][c] = NR[v][r] = NC[v][c] = NB[v][b] = 0;			// Failure, so backup
		}
	}
	return 0;		// no value was ok
}
function setPuzzle()	{
	var P = new Array(n2);		// Puzzle Array
	for (i=0; i <n2; i++) P[i]=new Array(n2);
	P[0] = [1,2,3, 9,0,0, 5,0,0];
	P[1] = [4,5,6, 0,1,0, 9,0,0];
	P[2] = [7,8,9, 0,0,5, 0,1,0];
	P[3] = [9,0,0, 1,2,3, 0,0,5];
	P[4] = [0,1,0, 4,5,6, 0,9,0];
	P[5] = [0,0,5, 7,8,9, 0,0,1];
	P[6] = [5,9,0, 0,0,0, 1,2,3];
	P[7] = [0,0,1, 0,9,0, 4,5,6];
	P[8] = [0,0,0, 5,0,1, 7,8,9];
	for (var r=0; r<9; r++) {
		for (var c=0; c<9; c++) {
			P[r][c] += "";
		}
	}
	readBoard(P);
}
function writeBoard() {
	for (var r=0; r<n2; r++) {
		for (var c=0; c<n2; c++) {
			document.getElementById('x' + r + c).value = B[r][c]; 	// write the board
		}
	}
}
function readBoard(P) {							// used whenever player may have changed board.
	var v, z; 
	for (var r=0; r<n2; r++) {
		for (var c=0; c<n2; c++) {
			var ID = 'x' + r + c;
			var sq = document.getElementById(ID); 	// read the board
			if (typeof(P)!='undefined')  sq.value = P[r][c];	
			z = sq.value;
			if (z=='' || '123456789'.indexOf(z) == -1) v = '0';
			else	v = z;
			if (B[r][c] != v)	{					// If changed it was the player, as program records its changes
				M[r][c] = 1;						// Player supplied the value
				B[r][c] = v;
			}
			if (v == '0')	M[r][c] = 0;		// Blanks are for the machine
			if (M[r][c]==1)	sq.style.background = "#9FF";	// player value
			else					sq.style.background = "#FFF"; // machine vlue			
		}
	}
}
function check() {
	var r, c;
	readBoard();
	for (r=0; r<n2; r++) {
		for (c=0; c<n2; c++) {
			if (Bok(r,c)) continue;
			message('mess', 'Conflict between two given values.');
			document.getElementById('x' + r + c).style.background = "#F33"; 	// read the board
			document.getElementById('x' + Rx + Cx).style.background = "#f33"; 	// read the board
			exit;
		}
	}
	message('mess', 'No conflicts in puzzle.');
	return 1;
}
function Bok(R,C) {
	var i = B[R][C];
	if (i=='0') return 1;			// empty cell is ok
	for (r=0; r<n2; r++) {
		if (r==R) continue;
		if (B[r][C]==i)  { Rx=r; Cx=C; return 0; }
	}
	for (c=0; c<n2; c++) { 
		if (c==C) continue;
		if (B[R][c]==i)  { Rx=R; Cx=c; return 0; }
	}
	r0 = R - R%n;	r3 = r0+n;
	c0 = C - C%n;  c3 = c0+n;
	for (r=r0; r<r3; r++) {
		for (c=c0; c<c3; c++) {
			if (r == R) continue;
			if (c == C) continue;
			if (B[r][c]==i)  { Rx=r; Cx=c; return 0; }
		}
	}
	return 1;
}
function clearX(what) {
	readBoard();
	clearBM(what);
	for (var r=0; r<n2; r++) 
	{
		for (var c=0; c<n2; c++) 
		{
			if (B[r][c]=='0')
			{
				var ID = 'x' + r + c;
				document.getElementById(ID).value = ""; 	// read the board
			}
		}
	}
	readBoard();
}
function clearBM(what) 
{	
	for (var r=0; r<n2; r++) 
		for (var c=0; c<n2; c++) 
		{
			if (what=='all')	B[r][c] = M[r][c] = 0;			// blank board
			if (what=='machine') 
				if (M[r][c] != 1)
					B[r][c] = M[r][c] = 0;
		}
}
function message(which, mess) {
	document.getElementById(which).innerHTML = mess;
} 
//-->