var board;
var savboard;
var hist;
var passboard;
var fillorder;
var cols;
var rows;
var boxes;
var onesa;
var rowmasks, colmasks, boxmasks;
var i, j, k;
var fill8 = 0;
var fillR = 0;
var fillC = 0;
var fillB = 0;
var pass = 0;
var passcounts = new Array();

// Figure out which 3x3 box each square belongs to
// Box is identified by upper left corner: 0, 3, 6, 27, 30, 33, ...

var boxheads = new Array(0,3,6,27,30,33,54,57,60);
var boxlist  = new Array(0,1,2,9,10,11,18,19,20);

function debug(s)
{
 var x = document.getElementById("debug");
 //x.innerHTML += s + "<BR>";
}
function compboxes()
{
 var i, j, k;
 boxes = new Array();
 for (i = 0; i < 81; i++)
   {
    j = Math.floor(i/27) * 27;
    k = j + Math.floor((i % 9) / 3) * 3;
    boxes[i] = k;
       // printf "%2d: %2d  ", $i, $k ;
       // if ($i % 9 == 8) {print "\n";}
   }
}


// How many 1-bits in the number (or mask) ?
function ones(x)
{
 var i;
 var onect = 0;
 for (i=1; i<10; i++)
   {
    if (x & (1 << i)) {onect++;}
   }
 return onect;
}

// Find which bit is turned on (if only 1)
function whichbit(n)
{
 var i = 0;
 var t = 1;
 while (1)
   {
    if (n & t) return i;
    t <<= 1;
    i++;
    if (i > 9) {return -1;}
   }
}

function savit()
{
 var i;
 savboard = new Array();
 for (i = 0; i<81; i++)
   {
    var x = document.getElementById("C" + i);
    savboard[i] = Number(x.value) + 0;
   }
 alert("Puzzle state saved");
}

function restorit()
{
 var i;
 remresults();
 for (i = 0; i<81; i++)
   {
    var x = document.getElementById("C" + i);
    x.value = (savboard[i] == 0) ? "" : savboard[i];
    centerit(x);
   }
}

function solveit()
{
 var changed = 1;
 var i, j, k, s;
 var r, c, b;
 var mask, maskr, maskc, maskb;
 var allbits = 1022;  // bits 1-9 0x3ff - 1
 var unfilled;
 var filled;
 fill8 = 0;
 fillR = 0;
 fillC = 0;
 fillB = 0;
 pass = 0;
 passcounts = new Array();
 hist = "";

// Initialize masks
for (i = 0; i<81; i++)
  {
   if (board[i] > 0)
     {
      j = Math.floor(i/9);
      rowmasks[j] |= 1 << board[i];
      j = i % 9;
      colmasks[j] |= 1 << board[i];
      j = boxes[i];
      boxmasks[j] |= 1 << board[i];
     }
  }

for (i = 0; i<9; i++)
  {
   debug(i + " " + rowmasks[i] + " " + colmasks[i]);
  }

 while (changed)
   {
    pass++;
    //print "Pass: $pass\n";
    changed = 0;
    filled = 0;

    // For each square, check combination of
    // row, column, box for 8 other numbers, 
    // leaving only 1 possibility
    for (i = 0; i<81; i++)
      {
       if (board[i] > 0) continue;
       r = Math.floor(i / 9);
       c = i % 9;
       b = boxes[i];
       maskr = rowmasks[r];
       maskc = colmasks[c];
       maskb = boxmasks[b];
       mask = ~(maskb | maskc | maskr) & allbits;
    //{print "> i: mask b:maskb c:maskc r:maskr\n";}
       if (onesa[mask] == 1)
         {
	  //printboard();
	  board[i] = whichbit(mask);
	  passboard[i] = ++fillorder;
	  //printf "Fill %2d: %d\n", i, board[i];
	  debug("Fill " + i + " " + board[i]);
	  boxmasks[b] |= 1 << board[i];
	  colmasks[c] |= 1 << board[i];
	  rowmasks[r] |= 1 << board[i];
	  changed = 1;
	  filled++;
	  fill8++;
	  hist += fillorder + ": [" + i + "]=" + board[i] + " E\n";
	 }
      }
    // Check rows, cols for only 1 poss for each number
    for (i=1; i<10; i++)
      {
       //print "Row Check for i\n";
       row:
       for (r=0; r<9; r++)
         {
	  if ((rowmasks[r] & (1 << i)) != 0)
	     continue;  // number already in row
	  j = -1;
	  for (c=0; c<9; c++)
	    {
	     s = r*9 + c;
	     if (board[s] > 0)
	        continue;
	     if ((colmasks[c] & (1 << i)) == 0  // number is not in this column
	     &&  (boxmasks[boxes[s]] & (1 << i)) == 0) // not in box either
	       {
		  {
		   //print "R Poss: r c\n";
		   if (j > -1)
		      continue row;  // non-unique chance of placement
		   j = c;
		  }
	       }
	    }
	  if (j > -1)
	    {
	     //printboard();
	     s = r * 9 + j;
	     board[s] = i;
	     passboard[s] = ++fillorder;
	     rowmasks[r] |= 1 << i;
	     colmasks[j] |= 1 << i;
	     boxmasks[boxes[s]] |= 1 << i;
	     changed = 1;
	     filled++;
	     //print "RC Fill: s board[s]\n";
	     debug("RC Fill: " + s + " " + board[s]);
	     fillR++;
	     hist += fillorder + ": [" + s + "]=" + board[s] + " R\n";
	    }
	 }
       //print "Col Check for i\n";
       col:
       for (c=0; c<9; c++)
	 {
	  if ((colmasks[c] & (1 << i)) != 0)
	     continue;  // number already in col
	  j = -1;
	  for (r=0; r<9; r++)
	    {
	     s = r*9 + c;
	     if (board[s] > 0)
	        continue;
	     if ((rowmasks[r] & (1 << i)) == 0  // number is not in this row
	     &&  (boxmasks[boxes[s]] & (1 << i)) == 0) // not in box either
	       {
	          { 
		    //print "C Poss: r c\n";
		    if (j > -1)
		       continue col; // non-unique chance of placement
		    j = r; 
		  }
	       }
	    }
	  if (j > -1)
	    {
	     //printboard();
	     s = j*9 + c;
	     board[s] = i;
	     passboard[s] = ++fillorder;
	     rowmasks[j] |= 1 << i;
	     colmasks[c] |= 1 << i;
	     boxmasks[boxes[s]] |= 1 << i;
	     changed = 1;
	     filled++;
	     //print "CC Fill: s board[s]\n";
	     debug("CC Fill: " + s + " " + board[s]);
	     fillC++;
	     hist += fillorder + ": [" + s + "]=" + board[s] + " C\n";
	    }
	 }
       // Check boxes for 1 possible place for each number
       box:
       for (bb in boxheads)
         {
	  b = boxheads[bb];
	  //print "Box check for i (b) boxmasks[b]\n";
	  //if (boxmasks[b] & (1 << i)) {print "Already in box\n";}
	  if ((boxmasks[b] & (1 << i)) != 0)
	     continue; // already in this box
	  j = -1;
	  for (kk in boxlist)
	    {
	     k = boxlist[kk];
	     s = b + k;
	     r = Math.floor(s/9);
	     c = s % 9;
	     if (board[s] == 0)
	       {
		//print "Square s board[s] r rowmasks[r] c colmasks[c] j:j\n";
		if ((rowmasks[r] & (1 << i)) == 0 &&
		    (colmasks[c] & (1 << i)) == 0)
		  {
		   //print "B Poss: s j\n";
		   if (j > -1)
		      continue box; // Second possible place
		   j = s;
		  }
	       }
	    }
	  if (j > -1)
	    {
	     // printboard();
	     board[j] = i;
	     passboard[j] = ++fillorder;
	     rowmasks[Math.floor(j/9)] |= 1 << i;
	     colmasks[j % 9] |= 1 << i;
	     boxmasks[b] |= 1 << i;
	     changed = 1;
	     filled++;
	     //print "BC Fill: j board[j]\n";
	     debug("BC Fill: " + j + " " + board[j]);
	     fillB++;
	     hist += fillorder + ": [" + j + "]=" + board[j] + " B\n";
	    }
	 }
      }

    //printboard();
    //print "Filled: filled\n";
    passcounts[pass] = filled;
    unfilled = 0;
    for (i = 0; i < 81; i++) if (board[i] == 0) unfilled++;
    if (unfilled == 0) break;
   }
 //print unfilled > 0 ? "Stuck!" : "Done";
 //print "\n";
}

function remresults()
{
 var x = document.getElementById("result");
 x.innerHTML = "Results:";
}
function showresult(what)
{
 var newrow = "<tr>\n";
 var endrow = "</tr>\n";
 var s ;
 var t ;
 var summary;
 var i,j,k;
 var unfilled = 0;
 for (i = 0; i < 81; i++) if (board[i] == 0) unfilled++;
 s = ((unfilled > 0) ? 
       "<h5>Partial Result</h5>" :
       "<h5>Solution: </h5>") +
       "\n<table border=0 cellpadding=1>\n";
 t = "<h5>Order in which cells filled:</h5>" +
 	"\n<table border = 0 cellpadding=1>\n";

 for (i in boxheads)
   {
    if (i % 3 == 0) {s += newrow; t += newrow;}
    b = boxheads[i];
    s += "<td><table class=sud1 border=1 cellpadding=2>";
    t += "<td><table class=sud3 border=1 cellpadding=4>";
    for (j in boxlist)
      {
       k = b + boxlist[j];
       if (j % 3 == 0) {s += newrow; t += newrow;}
       v = board[k];
       classs="";
       if (v == 0) {v = " ? "; classs=" class=sud2";}
       s += "<td" + classs + ">" + v + "</td>\n";
       v = passboard[k];
       width = j < 3 ? " width='33%'" : "";
       t += "<td" + width + " align=center>" + v + "</td>\n";
       if (j % 3 == 2) {s += endrow; t += endrow;}
      }
    s += "</table></td>\n";
    t += "</table></td>\n";
    if (i % 3 == 2) {s += endrow; t += endrow;}
   }
 s += "</table>\n";
 t += "</table>\n";

 summary = "<tr><td colspan=2>\n";
 var given = 81 - unfilled - fill8 - fillR - fillC - fillB;
 summary += "<span class=sud3>" + given + " given. ";
 if (unfilled > 0) 
    summary += unfilled + " unfilled, ";
 summary += pass + " passes [ ";
 for (i in passcounts)
   summary += passcounts[i] + " ";
 summary += "]<br>Filled " +
      fill8 + " by eights, " +
      fillR + " by rows, " +
      fillC + " by cols, " +
      fillB + " by boxes.</span>\n";
 summary += "</td></tr>";
 var x = document.getElementById("result");
 if (what != 'sol') s = "";
 x.innerHTML = "<table border=0 cellpadding=0 cellspacing=2>\n" +
 	"<tr><td>" + s + "</td>\n<td valign=top>" + t + "</td></tr>\n" +
	"</table>\n" +
	"<!--\n" + hist  + "-->\n" +
	summary + 
	"\n";
}

function doit(what)
{
   var i;
   board = new Array();
   passboard = new Array();
   fillorder = 0;
   rowmasks = new Array(0,0,0,0,0,0,0,0,0);
   colmasks = new Array(0,0,0,0,0,0,0,0,0);
   boxmasks = new Array();
   onesa = new Array();
   for (i=0; i<513; i++)
    {onesa[i] = ones(i);
     if (i < 81) boxmasks[i] = 0;}
   compboxes();

   for (i = 0; i<81; i++)
   {
    var x = document.getElementById("C" + i);
    board[i] = Number(x.value) + 0;
    passboard[i] = (board[i] > 0) ? "=" : "&nbsp;";
   }
   solveit();
   showresult(what);
}