var SUDOKUT_LIB = "sudoku-010.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 MSG;

var A = new Array(81);



function writeGrid()
{
var s="";
var BR = '<br style="height:8px">';
var j=0;
while (j<81)
  {
  var nameStr = "c" + j;
  j++;
  s += '<input class="sq" name="' + nameStr + '" value=" " size="1" type="text">&nbsp;';
  if (j==81) s += BR;
  else if ((j % 27) == 0) s += (BR + BR);
  else if ((j % 9) == 0) s += BR;
  else if ((j % 3) == 0) s += "&nbsp;&nbsp;";
  s += "\n";
  }
document.write(s);
}

function init()
{
F = document.sudokuform;
//MSG=document.getElementById("msgArea");
//assign A[3] = F.c3 etc by self executing code
for (var j=0;j<81;j++) eval("A[" + j + "]=F.c" + j);
clearAll();
}


function clear(x,n){for (var j=0;j<n;j++) x[j]=0;}

function duplicates(x)
{

var count=new Array(10);

//check rows
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;}
    }

//check columns
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;}
    }

//check boxes
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;
}//duplicates




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)
{
//MSG.innerHTML = 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;
}


//n = findPermittedVals(a, x, i);
//n == 0    cell is already filled
//n == -1   cell cannot be filled
//n == 1..9 number of permitted values for cell is n
function findPermittedVals(a, x, i)
{
clear(a,10);

//if cell's already filled there's no choice
if (x[i] > 0) {a[x[i]]=1; return 0;}

//x[i] is unfilled.  Initially set all values permitted
for (var j=1;j<=9;j++) a[j]=1;

var j,k,row,col,topleft,boxrow,boxcol;

row = Math.floor(i/9);//row number
col  = i % 9; //cell at top of same col
boxrow = 3*Math.floor(row/3); //row at top of same box
boxcol = 3*Math.floor(col/3); //col at left of same box
topleft = 9*boxrow + boxcol;//cell at topleft of same box

//zeroize x[i] if i is not a permitted value

//eliminate values in same row
k = 9*row;//cell at left of same row
for (j=0;j<9;j++) a[x[k + j]] = 0;

//and same col
k = col;
while (k < 81) {a[x[k]] = 0; k += 9;}

//and same box
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;

//count permissible values
var n=0;
for (j=1;j<=9;j++) n += a[j];
if (!n) return -1;//call cannot be filled
return n;
}

//use only when there is one permitted value
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;
  }
sho("");
//MSG.innerHTML = "";
}

function restore()
{
for (var j=0;j<81;j++)
  {
  if (saveval[j] == 0) A[j].value = "";
  else A[j].value=saveval[j];
  }
}

//returns -1 iff every cell contains either " " or "1" to "9"
//else returns index of an offending cell
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;
}


//insert values into those unfilled cells with only one legal entry
//do this repeatedly till the only unfilled cells have more than one legal value
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;
}//resolve

/*Telegraph 060324
9..5.8...
.5.3...1.
....7.5..
..9.2..41
41.....32
26..3.8..
..1.6....
.7...9.2.
...2.7..5
*/
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);

//make a working copy
for (var j=0;j<81;j++) cellval[j]=inputcellval[j];

//stats only
rRun++;
rDepth++; if (rDepth > maxDepth) maxDepth = rDepth;

cellChoice=-1;
while (1)
  {
  v = resolve(cellval);//set cells with only one possible value to that value

  //v = number of solved cells or -1 on impasse
  //this is the only point where progress, v is visible
  //as recursivesolve returns either a negative number or 81
  gcount++;
  if (!(gcount % 25)) sho("gcount="+ gcount + "  v=" + v + "  depth = "+ rDepth + " runs=" + rRun + " restarts="+restarts);


  //fail ie some cells have no possible legal values
  if (v < 0) {rDepth--;return -4;}

  //success?
  if (v == 81)//return updated input cell values
    {
    copy(inputcellval,cellval,81);
    rDepth--;
    return v;
    }

  //at this point we have no solution but the possiblity of one
  //the least number of permitted values for any cell is 2
  //since all those with only 1 value have been elimineted by resolve(..) above
  //pick a random cell with low number ("max") of possible values
  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);

  //step through the nPosVals possible values of cellval[cellChoice]
  value = 9;
  save = cellval[cellChoice];
  while (value)
    {
    if (a[value])
      {
      cellval[cellChoice] = value;

      //this is the only point of recursion
      v = recursivesolve(cellval);
      if (v<0) {rDepth--; return -12;}
      if (stop) {rDepth--; return -11;}
      if (v == 81)//return updated input cell values
        {
        copy(inputcellval,cellval,81);
        rDepth--; return 81;//announce success
        }
      }
      value--;
    }
  cellval[cellChoice] = save;//restore - if it'd worked we'd have skipped this line
  }//while (1)
end:
rDepth--;

//the only time it exits with a non-negative value for v is when v == 81
return v;
}//recursivesolve



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;
  }



//returns sum of these bitmaps
//1 - table contains good values
//2 - rows good
//4 - cols good
//8 - boxes good
//returns 15 if puzzle properly solved
function solutionQualityCode(x)
{
var entriesgood=0,rowsgood=0,colsgood=0,boxesgood=0;

entriesgood = tableContainsOnlyValues(x,1,9);
if (!entriesgood) return 0;

//at this point the table contains only values 1..9

var count = new Array(10);

//count row errors
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;
}




//solve with recursivesolve, restarting if necessary
function solve(x)
{
var xx = new Array(81);//temp save
var k=-1;
rRun=rDepth=maxDepth=restarts=0;
copy(xx,x,81);
stop = 0;
gcount=0;
while (k < 0)
  {
  k = recursivesolve(x);//xxx
  if (stop)
    {
    copy(x,xx,81);
    rRun=rDepth=maxDepth=0;
    restarts++;
    stop=0;
    }
  }
sho("done");
return solutionQualityCode(x);
}//solve(x);


//solve and report to punter
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));
}


//get values from squares, report illegal entries, and solveSudoku if OK
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);//calls solve() which calls recursiveSolve()
}