var SUDOKUT_LIB = "sudoku-008.js";var test = 0;var cellval = new Array(81);var saveval = new Array(81);
var rRun,maxRun,rDepth,restarts,stop,gcount;var MAXDEPTH = 50;var MAXRUN = 150;var F;
var A = new Array(81);function init(){ F = document.myform;A[0]=F.c0;A[1]=F.c1;A[2]=F.c2;
A[3]=F.c3;A[4]=F.c4;A[5]=F.c5;A[6]=F.c6;A[7]=F.c7;A[8]=F.c8;A[9]=F.c9;A[10]=F.c10;
A[11]=F.c11;A[12]=F.c12;A[13]=F.c13;A[14]=F.c14;A[15]=F.c15;A[16]=F.c16;A[17]=F.c17;
A[18]=F.c18;A[19]=F.c19;A[20]=F.c20;A[21]=F.c21;A[22]=F.c22;A[23]=F.c23;A[24]=F.c24;
A[25]=F.c25;A[26]=F.c26;A[27]=F.c27;A[28]=F.c28;A[29]=F.c29;A[30]=F.c30;A[31]=F.c31;
A[32]=F.c32;A[33]=F.c33;A[34]=F.c34;A[35]=F.c35;A[36]=F.c36;A[37]=F.c37;A[38]=F.c38;
A[39]=F.c39;A[40]=F.c40;A[41]=F.c41;A[42]=F.c42;A[43]=F.c43;A[44]=F.c44;A[45]=F.c45;
A[46]=F.c46;A[47]=F.c47;A[48]=F.c48;A[49]=F.c49;A[50]=F.c50;A[51]=F.c51;A[52]=F.c52;
A[53]=F.c53;A[54]=F.c54;A[55]=F.c55;A[56]=F.c56;A[57]=F.c57;A[58]=F.c58;A[59]=F.c59;
A[60]=F.c60;A[61]=F.c61;A[62]=F.c62;A[63]=F.c63;A[64]=F.c64;A[65]=F.c65;A[66]=F.c66;
A[67]=F.c67;A[68]=F.c68;A[69]=F.c69;A[70]=F.c70;A[71]=F.c71;A[72]=F.c72;A[73]=F.c73;
A[74]=F.c74;A[75]=F.c75;A[76]=F.c76;A[77]=F.c77;A[78]=F.c78;A[79]=F.c79;A[80]=F.c80;
clearAll();}function clear(x,n){for (var j=0;j<n;j++)x[j]=0;}function duplicates(x)
{ var count=new Array(10);for (var row=0;row<9;row++){ clear(count,10);for (var col=0;col<9;col++)count[x[9*row + col]]++;
for (var k=1;k<=9;k++)if (count[k] > 1){alert("row " + (row+1)+ " contains duplicates");return true;}
}for (var col=0;col<9;col++){ clear(count,10);for (var row =0;row <9;row++)count[x[9*row + col]]++;
for (var k=1;k<=9;k++)if (count[k] > 1){alert("column " + (col+1)+ " contains duplicates");return true;}
}for (var r=0;r<3;r++){ for (var c=0;c<3;c++){ clear(count,10);var row = 3*r;var col = 3*c;
for (var dr=0;dr<3;dr++){ for (var dc=0;dc<3;dc++)count[x[9*(row+dr)+ col + dc]]++;
}for (var k=1;k<=9;k++)if (count[k] > 1){alert("box " + (3*r+c+1)+ " contains duplicates");return true;}
}}return false;}function yes(question){ return confirm("Please Reply\n\n\n" + question + "\n\n\n");
}function test1(){ alert("A[1] = " + A[1].value);}function sho(s){ F.msg.value = s;
}function copy(y,x,n){ for (var j=0;j<n;j++)y[j]=x[j];}function setall(y,n,val){ for (var j=0;j<n;j++)y[j]=val;
}function findPermittedVals(a,x,i){ clear(a,10);if (x[i] > 0){a[x[i]]=1;return 0;}
for (var j=1;j<=9;j++)a[j]=1;var j,k,row,col,topleft,boxrow,boxcol;row = Math.floor(i/9);
col = i % 9;boxrow = 3*Math.floor(row/3);boxcol = 3*Math.floor(col/3);topleft = 9*boxrow + boxcol;
k = 9*row;for (j=0;j<9;j++)a[x[k + j]] = 0;k = col;while (k < 81){a[x[k]] = 0;k += 9;}
k = topleft;for (j=0;j<3;j++)a[x[k+j]] = 0;k += 9;for (j=0;j<3;j++)a[x[k+j]] = 0;
k += 9;for (j=0;j<3;j++)a[x[k+j]] = 0;var n=0;for (j=1;j<=9;j++)n += a[j];if (!n)return -1;
return n;}function permittedValue(a){ var k=1;while (!a[k])k++;return k;}function clearAll()
{ for (var j=0;j<81;j++){ A[j].value="";saveval[j]=0;}F.msg.value="";}function restore()
{ for (var j=0;j<81;j++){ if (saveval[j] == 0)A[j].value = "";else A[j].value=saveval[j];
}}function getCellValuesFromSquaresOK(x){ for (var j=0;j<81;j++){ var t = A[j].value;
if (t == " ")x[j]=0;else if (t == "")x[j]=0;else { if (isNaN(t))return j;var n = parseInt(t);
if (n < 1)return j;if (n > 9)return j;x[j]=n;}}return -1;}function resolve(cellValue)
{ var nSolved,nSolvedThisPass;var OK=1;var a = new Array(10);do { nSolved=0;nSolvedThisPass=0;
for (var cell=0;cell<81;cell++){ if (cellValue[cell] > 0)nSolved++;else { var n = findPermittedVals(a,cellValue,cell);
if (n == 1){ nSolvedThisPass++;nSolved++;cellValue[cell] = permittedValue(a);}else if (n < 0 )OK=false;
}}}while ((nSolvedThisPass > 0)&& OK);if (!OK)return -1;else return nSolved;}function testGrid()
{ var t = new Array(81);clear(t,81);t[0]=9;t[3]=5;t[5]=8;t[10]=5;t[12]=3;t[16]=1;
t[22]=7;t[24]=5;t[29]=9;t[31]=2;t[34]=4;t[35]=1;t[36]=4;t[37]=1;t[43]=3;t[44]=2;
t[45]=2;t[46]=6;t[49]=3;t[51]=8;t[56]=1;t[58]=6;t[64]=7;t[68]=9;t[70]=2;t[75]=2;t[77]=7;t[80]=5;
for (var j=0;j<81;j++)if (t[j]==0)A[j].value="";else A[j].value=t[j];}function millisecs()
{ var d=new Date();return d.getTime();}function NF(number,fieldsize,decimals){ var t = number.toFixed(decimals);
var L = fieldsize - t.length;while (L-- > 0)t = ' ' + t;return t;}function recursivesolve(inputcellval)
{ var v = -1;if ((rRun >= MAXRUN)|| (rDepth > MAXDEPTH)){stop=true;return -1;}var cellval = new Array(81);
var cellChoice,nPosVals,value,save,max,count;var OK;var a = new Array(10);clear(a,10);
for (var j=0;j<81;j++)cellval[j]=inputcellval[j];rRun++;rDepth++;if (rDepth > maxDepth)maxDepth = rDepth;
cellChoice=-1;while (1){ v = resolve(cellval);gcount++;if (!(gcount % 25))sho("gcount="+ gcount + " v=" + v + " depth = "+ rDepth + " runs=" + rRun + " restarts="+restarts);
if (v < 0){rDepth--;return -4;}if (v == 81){ copy(inputcellval,cellval,81);rDepth--;
return v;}max=2;count=0;do { count++;if (!(count % 100)){ if (count > 1000){rDepth--;return -10;}
if (max < 9)max++;}cellChoice = Math.floor(81*Math.random());nPosVals = findPermittedVals(a,cellval,cellChoice);
OK = ((nPosVals > 1)&& (nPosVals <= max));}while (!OK);value = 9;save = cellval[cellChoice];
while (value){ if (a[value]){ cellval[cellChoice] = value;v = recursivesolve(cellval);
if (v<0){rDepth--;return -12;}if (stop){rDepth--;return -11;}if (v == 81){ copy(inputcellval,cellval,81);
rDepth--;return 81;}}value--;}cellval[cellChoice] = save;}end: rDepth--;return v;
}function tableContainsOnlyValues(x,n1,n2){ for (var j=0;j<81;j++){ if (x[j] < n1)return 0;
if (x[j] > n2)return 0;}return 1;}function solutionQualityCode(x){ var entriesgood=0,rowsgood=0,colsgood=0,boxesgood=0;
entriesgood = tableContainsOnlyValues(x,1,9);if (!entriesgood)return 0;var count = new Array(10);
for (var row=0;row<9;row++){ clear(count,10);for (var col=0;col<9;col++){ var cell = 9*row + col;
count[x[cell]]++;}rowsgood =1;for (var k=1;k<=9;k++)if (count[k] != 1)rowsgood=0;
}for (var col=0;col<9;col++){ clear(count,10);for (var row =0;row <9;row++){ var cell = 9*row + col;
count[x[cell]]++;}colsgood=1;for (var k=1;k<=9;k++)if (count[k] != 1)colsgood=0;
}for (var r=0;r<3;r++){ for (var c=0;c<3;c++){ clear(count,10);var row = 3*r;var col = 3*c;
for (var dr=0;dr<3;dr++){ for (var dc=0;dc<3;dc++){ count[x[9*(row+dr)+ col + dc]]++;
}}boxesgood=1;for (var k=1;k<=9;k++)if (count[k] != 1)boxesgood=0;}}var q=0;if (entriesgood)q += 1;
if (rowsgood)q += 2;if (colsgood)q += 4;if (boxesgood)q += 8;return q;}function solve(x)
{ var xx = new Array(81);var k=-1;rRun=rDepth=maxDepth=restarts=0;copy(xx,x,81);stop = 0;
gcount=0;while (k < 0){ k = recursivesolve(x);if (stop){ copy(x,xx,81);rRun=rDepth=maxDepth=0;
restarts++;stop=0;}}sho("done");return solutionQualityCode(x);}function solveSudoku()
{ var quality="OK";var ms=millisecs();q = solve(cellval);ms=millisecs()- ms;if (q != 15)quality="BAD q=" + q;
for (var j=0;j<81;j++)A[j].value = cellval[j];sho("runs=" + rRun + " depth=" + maxDepth + " restarts=" + restarts + " solution=" + quality + " secs=" + NF(0.001*ms,4,2));
}function solveit(){ var k = getCellValuesFromSquaresOK(cellval);if (k != -1){ var r = 1 + Math.floor(k/9);
var c = 1 + (k % 9);alert("cell in row " + r + ",column " + c + " contains the illegal entry '" + A[k].value + "'");
return;}if (duplicates(cellval))return;copy(saveval,cellval,81);solveSudoku(cellval);
}