/*
SuDoku Solver by Logic v1.31
Copyright (C) Peter Wake 2005

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

The GNU General Public License can be seen at
  http://www.gnu.org/licenses/gpl.html

Or contact the author via the website link at
  http://www.sudokusolver.co.uk
*/


//=============================================================================
// Contributors
// ------------
// PW - Initial coding
// ATC - Alan Chambers (alpha tango charlie at delcam dot com)
// PW - Added multilingual capability via jstr variable
// CO - Swordfish (Method F2) //NOW DEPRECATED
// PW - Multilingual adaption for far eastern texts, change jstr to mlText
//-----------------------------------------------------------------------------


border1="#303090";
border2="#9090FF";
shading1="#FFFFFF";


function Sudoku(startGridDiv,workingGridDiv,notesName)
{
  this.xName=mlText.xName;
  this.yName=mlText.yName;
  this.startVals="_3___1___x__6____5_x5_____983x_8___63_2x____5____x9_38___6_x714_____9x_2____8__x___4___3_";
  this.lastSubmittedGrid=this.startVals;

  this.matrix=new Array();
  this.matrixEl=new Array();
  this.matrixColor=new Array();
  this.startMatrix=new Array();
  this.hasChangedFlag=false;
  this.solvedCount=0;
  this.startGridDiv=startGridDiv;
  this.workingGridDiv=workingGridDiv;
  if(document.frames) this.notesDoc=document.frames(notesName).document;
  if(document.getElementById(notesName).contentDocument) this.notesDoc=document.getElementById(notesName).contentDocument;

  this.found=null;
  this.lastFoundX=0;
  this.lastFoundY=0;
  this.step=false;
  this.breakOut=false;
  this.lastHighlightedX=null;
  this.lastHighlightedY=null;

  this.solutions=0;
  this.difficultyScore=0;
  this.guesses=0;
  this.latestSolution="";
  this.doAriadne=true;
  this.returnFirstAnswer=true;
  this.stopAfterTwoSolutions=true;
  this.doAlert=true;

  this.lsEl=null;

  var x,y;
  for(y=0;y<9;y++)
  {
    this.matrix[y]=new Array();
    this.matrixEl[y]=new Array();
    this.matrixColor[y]=new Array();
    this.startMatrix[y]=new Array();
  }
  this.initialiseDivs();

  this.bufferNotes="";
  this.lastNote="";
  this.lastNoteButOne="";
  this.notesDoc.body.innerHTML=mlText.notes+"<br>";
}

/////////////////////////////////////////////////////////////////////////////////////////////////
//
//
//  UTILITY FUNCTIONS
//
/////////////////////////////////////////////////////////////////////////////////////////////////




Sudoku.prototype.cellString=function(x,y)
{
  return "["+this.yName[y]+this.xName[x]+"]";
}

Sudoku.prototype.parseString=function(str,replaceObj)
{
  var el,myReg;
  for(el in replaceObj)
  {
    if(typeof replaceObj[el]=='function') continue;
    myReg=new RegExp("%"+el+"%","g");
    str=str.replace(myReg,replaceObj[el]);
  }
  return str;
}

Sudoku.prototype.addNote=function(str,replaceObj)
{
  str=this.parseString(str,replaceObj);
  this.lastNoteButOne=this.lastNote;
  if(this.lastNoteButOne && this.lastNoteButOne.indexOf("<pre>")!=-1) this.lastNoteButOne="";
  this.lastNote=str;
  this.bufferNotes+=str+"<br>";
}

Sudoku.prototype.echoNotes=function()
{
  this.notesDoc.body.innerHTML+=this.bufferNotes;
  this.bufferNotes="";
}

Sudoku.prototype.clearNoteBuffer=function()
{
  this.bufferNotes="";
}



Sudoku.prototype.statusNote=function()
{
  this.addNote("<pre>"+this.statusNoteText("<br>")+"</pre>");
}
Sudoku.prototype.statusNoteText=function(eolTxt)
{
  var x,y,a0,sps;
  sps="          ";

  a0="   |  ";
  for(x=0;x<9;x++)
  {
    a0+=this.xName[x]+"         ";
  }
  a0+=eolTxt;
  a0+="---+--";
  for(x=0;x<9;x++)
  {
    a0+="----------";
  }
  a0+=eolTxt;
  for(y=0;y<9;y++)
  {
    a0 += this.yName[y]+"  |  ";
    for(x=0;x<9;x++)
    {
      a0+=this.matrix[y][x];
      a0+=sps.substring(0,10-this.matrix[y][x].length);
    }
    a0+=eolTxt;
  }
  return a0;
}

Sudoku.prototype.startMethodNote=function(methodCode)
{
  this.addNote("==============================");
  this.addNote(mlText.startingSolveMethod,{methodCode:methodCode});
  this.statusNote();
}

Sudoku.prototype.endMethodNote=function(methodCode)
{
  if(this.step==true) this.refreshWorkingGrid();
  this.addNote(mlText.endingSolveMethod,{methodCode:methodCode});
  this.addNote("==============================");
}



Sudoku.prototype.resetWorkingGrid=function()
{
  var x,y;
  for(y=0;y<9;y++)
  {
    for(x=0;x<9;x++)
    {
      this.matrixColor[y][x]='#FFFFFF';
      this.matrixEl[y][x].style.fontWeight='normal';
      this.matrixEl[y][x].style.color='#404040';
      this.matrix[y][x]='123456789';
      this.hasChangedFlag=true;
    }
  }
  this.lastHighlightedX=null;
  this.lastHighlightedY=null;

  this.refreshWorkingGrid();
  this.notesDoc.body.innerHTML=mlText.notes+"<br>";
  this.addNote(mlText.resetWorkingGrid);
  this.solvedCount=0;
  this.difficultyScore=0;
  this.guesses=0;
}




Sudoku.prototype.clearStartGrid=function()
{
  var csg=confirm(mlText.sureClearStartGrid);
  if(csg!=true) return;
  var x,y;
  for(y=0;y<9;y++)
  {
    for(x=0;x<9;x++)
    {
      formEl=document.getElementById("sgd_"+x+"_"+y);
      formEl.value="";
    }
  }
}

Sudoku.prototype.clearWorkingGrid=function()
{
  var x,y;
  for(y=0;y<9;y++)
  {
    for(x=0;x<9;x++)
    {
      formEl=document.getElementById("sgw_"+x+"_"+y);
      formEl.value="";
    }
  }
}


Sudoku.prototype.initialiseDivs=function()
{
  this.startGridDiv.innerHTML=this.showHTML("\"<input type='text' id='sgd_\"+x+\"_\"+y+\"' value='' size='1' maxlength='1' class='startGrid'>\"");
  this.workingGridDiv.innerHTML=this.showHTML("\"<input type='text' id='sgw_\"+x+\"_\"+y+\"' value='' size='9' maxlength='9' class='workingGrid'>\"");
  for(y=0;y<9;y++)
  {
    for(x=0;x<9;x++)
    {
      this.matrixEl[y][x]=document.getElementById("sgw_"+x+"_"+y);
    }
  }
  this.resetWorkingGrid();
  if(loadCurrentGrid()==true) return; //if available
  if(mostPopularGridLoaded==true)
  {
    setSudokuString(mostPopularGrid,"x");
    this.lastSubmittedGrid=mostPopularGrid;
    return;
  }
  setSudokuString(this.startVals,"x");
  sudokuLoaded=true;
}




Sudoku.prototype.refreshWorkingGrid=function()
{
  for(y=0;y<9;y++)
  {
    for(x=0;x<9;x++)
    {
      this.matrixEl[y][x].value=this.matrix[y][x];
      this.matrixEl[y][x].style.backgroundColor=this.matrixColor[y][x];
    }
  }
}




Sudoku.prototype.showHTML=function(evalStr)
{
  var a0,styleStr;

  a0="<table cellpadding=0 cellspacing=0>";
  var x,y;
  a0+="<tr>";
  a0+="<td></td>";
  for(x=0;x<9;x++)
  {
    a0+="<td>"+this.xName[x]+"</td>";
  }
  a0+="</tr>";

  for(y=0;y<9;y++)
  {
    a0+="<tr>";
    a0+="<td>"+this.yName[y]+"</td>";
    for(x=0;x<9;x++)
    {
      styleStr=" style='border-color:";
      styleStr+=(y%3==0)?border1:border2;
      styleStr+=" ";
      styleStr+=(x%3==2)?border1:border2;
      styleStr+=" ";
      styleStr+=(y%3==2)?border1:border2;
      styleStr+=" ";
      styleStr+=(x%3==0)?border1:border2;
      styleStr+="'";
      a0+="<td"+styleStr+">"+eval(evalStr)+"</td>";
    }
    a0+="</tr>";
  }
  a0+="</table>";
  return a0;
}






/////////////////////////////////////////////////////////////////////////////////////////////////
//
//
//  SUDOKU-SPECIFIC UTILITY FUNCTIONS
//
/////////////////////////////////////////////////////////////////////////////////////////////////



Sudoku.prototype.runStartGrid=function()
{
  var x,y;

  this.breakOut=false;

  this.addNote("==============================");
  this.addNote("<b>"+mlText.runningStartGrid+"</b>");

  for(y=0;y<9;y++)
  {
    for(x=0;x<9;x++)
    {
      formEl=document.getElementById("sgd_"+x+"_"+y);
      if(formEl.value==" ") formEl.value="";
      if(formEl.value!="")
      {
        this.startMatrix[y][x]=formEl.value;
        this.set(x,y,formEl.value,true,true);
      }
      if(this.breakOut) return this.refreshWorkingGrid();
    }
  }
  this.refreshWorkingGrid();
}



Sudoku.prototype.getMatrixString=function()
{
  var a0,x,y;

  a0="";
  for(y=0;y<9;y++)
  {
    for(x=0;x<9;x++)
    {
      a0+=this.matrix[y][x];
      if(x!=8) a0+=",";
    }
    if(y!=8) a0+="+";
  }
  return a0;
}



Sudoku.prototype.setMatrixString=function(a0)
{
  var x,y,sArr,tArr;

  sArr=a0.split("+");
  for(y=0;y<9;y++)
  {
    tArr=sArr[y].split(",");
    for(x=0;x<9;x++)
    {
      this.matrix[y][x]=tArr[x];
    }
  }
  return;
}



Sudoku.prototype.isInvalidSolutionSubset=function(setArray)
{
  setArray.sort();
  for(i=0;i<setArray.length;i++)
  {
    if(setArray[i].toString()!=(i+1).toString()) return true;
  }
  return false;
}

Sudoku.prototype.checkSolution=function()
{
  var ix1,ix2,ix3,ix4,row,col,block;

  for(ix1=0;ix1<3;ix1++)
  {
    for(ix2=0;ix2<3;ix2++)
    {
      row=new Array(); col=new Array(); block=new Array();
      for(ix3=0;ix3<3;ix3++)
      {
        for(ix4=0;ix4<3;ix4++)
        {
          row[ix3*3+ix4]=this.matrix[ix1*3+ix2][ix3*3+ix4];
          col[ix3*3+ix4]=this.matrix[ix3*3+ix4][ix1*3+ix2];
          block[ix3*3+ix4]=this.matrix[ix1*3+ix3][ix2*3+ix4];
        }
      }
      if(this.isInvalidSolutionSubset(row) || this.isInvalidSolutionSubset(col) || this.isInvalidSolutionSubset(block)) return false;
    }
  }
  return true;
}

Sudoku.prototype.explainAndPause=function(highlightArray)
{
  var i,y,x;

  this.refreshWorkingGrid();

  for(i=0;i<highlightArray.length;i++)
  {
    if(highlightArray[i][0]=='row')
    {
      for(x=0;x<9;x++)
      {
        this.matrixEl[highlightArray[i][1]][x].style.backgroundColor=highlightArray[i][2];
      }
    }
    if(highlightArray[i][0]=='col')
    {
      for(y=0;y<9;y++)
      {
        this.matrixEl[y][highlightArray[i][1]].style.backgroundColor=highlightArray[i][2];
      }
    }
    if(highlightArray[i][0]=='block')
    {
      for(x=0;x<3;x++)
      {
        for(y=0;y<3;y++)
        {
          this.matrixEl[y+highlightArray[i][2]][x+highlightArray[i][1]].style.backgroundColor=highlightArray[i][3];
        }
      }
    }
    if(highlightArray[i][0]=='cell')
    {
      this.matrixEl[highlightArray[i][2]][highlightArray[i][1]].style.backgroundColor=highlightArray[i][3];
    }
  }

  var a0=prompt(this.lastNoteButOne,this.lastNote);
  if (a0==null)
  {
    this.breakOut=true;
  }
}
Sudoku.prototype.shade=function(x,y)
{
  this.matrixColor[y][x]=shading1;
  this.matrixEl[y][x].style.backgroundColor=this.matrixColor[y][x];
  this.matrixEl[y][x].style.color='#000000';
}
Sudoku.prototype.set=function(x,y,val,test,dontReport)
{
  var ix,iy,xBlockStart,yBlockStart;

  if(test && this.matrix[y][x]==val.toString())
  {
    if(dontReport==null || dontReport!=true) this.addNote(mlText.wantToSetCell,{cell:this.cellString(x,y),val:val});
    return;
  }

  this.solvedCount++;

  this.addNote(mlText.setCell,{cell:this.cellString(x,y),val:val,togo:(81-this.solvedCount)});

  if(this.solvedCount==81)
  {
    this.shade(x,y);
    this.addNote(mlText.checkValid);
    this.statusNote();
    if(this.checkSolution()!=true)
    {
      throw mlText.invalidSolution;
    }
    this.solutions++;
    this.latestSolution=this.getMatrixString();
    this.addNote(mlText.validSolution);
    this.addNote(mlText.difficultyScore,{difficultyScore:this.difficultyScore});
    this.addNote(mlText.numberOfGuesses,{guesses:this.guesses});
    return;
  }

  xBlockStart=3*parseInt(x/3);
  yBlockStart=3*parseInt(y/3);

  if(this.step) this.explainAndPause(new Array(new Array('block',xBlockStart,yBlockStart,'#8470FF'),new Array('row',y,'#98FB98'),new Array('col',x,'pink'),new Array('cell',x,y,'#FFD700')));

  this.matrix[y][x]=val.toString();
  this.shade(x,y);

  this.hasChangedFlag=true;

  for(ix=0;ix<9;ix++)
  {
    if(ix!=x) this.remove(ix,y,val);
  }
  for(iy=0;iy<9;iy++)
  {
    if(iy!=y) this.remove(x,iy,val);
  }

  for(ix=xBlockStart;ix<xBlockStart+3;ix++)
  {
    for(iy=yBlockStart;iy<yBlockStart+3;iy++)
    {
      if(ix!=x && iy!=y) this.remove(ix,iy,val);
    }
  }


}

Sudoku.prototype.isValAtXY=function(x,y,val)
{
  var vpos=this.matrix[y][x].indexOf(val);
  if(vpos>=0) return true;
  return false;
}

Sudoku.prototype.remove=function(x,y,val)
{
  var vpos=this.matrix[y][x].indexOf(val);
  if(vpos>=0)
  {
    if(this.matrix[y][x].length==1)
    {
      throw this.parseString(mlText.invalidSolutionCantDelete,{val:val,cell:this.cellString(x,y)});
    }
    this.matrix[y][x]=this.matrix[y][x].substr(0,vpos)+this.matrix[y][x].substr(vpos+1);
    this.hasChangedFlag=true;
    if(this.matrix[y][x].length==1)
    {
      this.addNote(mlText.removing1,{val:val,cell:this.cellString(x,y),matrixValue:this.matrix[y][x]});
      if(document.getElementById("sgd_"+x+"_"+y)!=this.matrix[y][x]) this.difficultyScore+=1;
      this.set(x,y,this.matrix[y][x],false);
    }
  }
}




Sudoku.prototype.columnCount=function(x,vals)
{
  this.found=null;
  this.found=new Array();
  vals=vals.toString();
  var vp,vc;
  var y;
  var ct=0;
  for(y=0;y<9;y++)
  {
    vc=0;
    for(vp=0;vp<vals.length;vp++)
    {
      if(this.matrix[y][x].indexOf(vals.charAt(vp))>=0)
      {
        vc++;
      }
    }
    if(vc==vals.length)
    {
      ct++;
      this.lastFoundY=y;
      this.found.push(new Array(x,y));
    }
  }
  return ct;
}




Sudoku.prototype.rowCount=function(y,vals)
{
  this.found=null;
  this.found=new Array();
  vals=vals.toString();
  var vp,vc;
  var x;
  var ct=0;
  for(x=0;x<9;x++)
  {
    vc=0;
    for(vp=0;vp<vals.length;vp++)
    {
      if(this.matrix[y][x].indexOf(vals.charAt(vp))>=0)
      {
        vc++;
      }
    }
    if(vc==vals.length)
    {
      ct++;
      this.lastFoundX=x;
      this.found.push(new Array(x,y));
    }
  }
  return ct;
}




Sudoku.prototype.blockCount=function(bx,by,vals)
{
  this.found=null;
  this.found=new Array();
  vals=vals.toString();
  var vp,vc;
  var x,y;
  var ct=0;

  for(x=bx*3;x<3+bx*3;x++)
  {
    for(y=by*3;y<3+by*3;y++)
    {
      vc=0;
      for(vp=0;vp<vals.length;vp++)
      {
        if(this.matrix[y][x].indexOf(vals.charAt(vp))>=0)
        {
          vc++;
        }
      }
      if(vc==vals.length)
      {
        ct++;
        this.lastFoundX=x;
        this.lastFoundY=y;
        this.found.push(new Array(x,y));
      }
    }
  }
  return ct;
}



//Related to Method C
//looks in foundCountOf array to see if there are any elements containing unique
Sudoku.prototype.findUnique=function(foundCountOf,c)
{
  var curEl,compareEl,matches,i,j,matchedEl,elimOne,newSet;
  elimOne=false;
  while(foundCountOf.length>=c)
  {
    //pull off the first element
    curEl = foundCountOf.shift();
    //now for all the other elements
    matches=null;
    matches=new Array();
    for(i=0;i<foundCountOf.length;i++)
    {
      compareEl=foundCountOf[i];
      matchedEl=true;
      //all the xy positions of all the elements' found positions must match
      for(j=0;j<c;j++)
      {
        if(curEl[1][j][0]!=compareEl[1][j][0] || curEl[1][j][1]!=compareEl[1][j][1])
        {
          matchedEl=false;
          break;
        }
      }
      if(matchedEl)
      {
        matches.push(compareEl);
      }
    }
    if(matches.length==c-1) //there are exactly c matches - so if 3 numbers, with 3 count, in same cells
    {
      newSet=curEl[0].toString();
      for(j=0;j<c-1;j++)
      {
        newSet+=matches[j][0].toString();
      }
      elimOne=false;
      for(j=0;j<c;j++)
      {
        if(this.matrix[curEl[1][j][1]][curEl[1][j][0]]!=newSet) elimOne=true;
      }
      if(elimOne)
      {
        this.addNote(mlText.foundMulticountSet,{newSet:newSet});
        this.difficultyScore+=16;
        if(this.step)
        {
          multiCountSet=new Array();
          for(j=0;j<c;j++)
          {
            multiCountSet[j]=new Array('cell',curEl[1][j][0],curEl[1][j][1],'#8470FF');
          }
          this.explainAndPause(multiCountSet);
        }
        for(j=0;j<c;j++)
        {
          this.addNote(mlText.setToNewSet,{cell:this.cellString(curEl[1][j][0],curEl[1][j][1]),newSet:newSet});
          this.matrix[curEl[1][j][1]][curEl[1][j][0]]=newSet;
          this.hasChangedFlag=true;
        }
      }
    }
  }
  return elimOne;
}


/////////////////////////////////////////////////////////////////////////////////////////////////
//
//
//  SUDOKU SOLVE METHOD CONTROLLERS
//
/////////////////////////////////////////////////////////////////////////////////////////////////



//=============================================================================
// History
// Who When     What
// --- -------- ---------------------------------------------------------------
// ATC 06/09/05 Substituted MethodD2 for MethodD. This includes the extension
//              suggested by John MacLeod.
//-----------------------------------------------------------------------------
Sudoku.prototype.logicSolve=function()
{
  this.hasChangedFlag=true;
  while(this.breakOut==false && this.hasChangedFlag==true && this.solvedCount<81)
  {
    this.echoNotes();
    this.hasChangedFlag=false;
    this.solveMethodA();
    if(this.hasChangedFlag==true) this.echoNotes();
    if(this.solvedCount==81 || this.breakOut==true) continue;

    this.clearNoteBuffer();
    this.solveMethodB();
    if(this.hasChangedFlag==true || this.breakOut==true) continue;

    this.clearNoteBuffer();
    this.solveMethodC(2);
    if(this.hasChangedFlag==true || this.breakOut==true) continue;

    this.clearNoteBuffer();
    this.solveMethodC(3);
    if(this.hasChangedFlag==true || this.breakOut==true) continue;

    this.clearNoteBuffer();
    this.solveMethodC(4);
    if(this.hasChangedFlag==true || this.breakOut==true) continue;

    this.clearNoteBuffer();
    this.solveMethodC(5);
    if(this.hasChangedFlag==true || this.breakOut==true) continue;

    this.clearNoteBuffer();
    this.solveMethodC(6);
    if(this.hasChangedFlag==true || this.breakOut==true) continue;

    this.clearNoteBuffer();
    this.solveMethodC(7);
    if(this.hasChangedFlag==true || this.breakOut==true) continue;

    this.clearNoteBuffer();
    this.solveMethodC(8);
    if(this.hasChangedFlag==true || this.breakOut==true) continue;

    this.clearNoteBuffer();
    this.hasChangedFlag=false;
    this.solveMethodD2(2,32);
    if(this.hasChangedFlag==true || this.breakOut==true) continue;

    this.clearNoteBuffer();
    this.hasChangedFlag=false;
    this.solveMethodD2(3,48);
    if(this.hasChangedFlag==true || this.breakOut==true) continue;

    this.clearNoteBuffer();
    this.hasChangedFlag=false;
    this.solveMethodD2(4,64);
    if(this.hasChangedFlag==true || this.breakOut==true) continue;

    this.clearNoteBuffer();
    this.hasChangedFlag=false;
    this.solveMethodF3(2,48);
    if(this.hasChangedFlag==true || this.breakOut==true) continue;

    this.clearNoteBuffer();
    this.hasChangedFlag=false;
    this.solveMethodF3(3,64);
    if(this.hasChangedFlag==true || this.breakOut==true) continue;

    this.clearNoteBuffer();
    this.hasChangedFlag=false;
    this.solveMethodF3(4,64);
    if(this.hasChangedFlag==true || this.breakOut==true) continue;

    this.clearNoteBuffer();
    this.hasChangedFlag=false;
    this.solveMethodF3(5,64);
    if(this.hasChangedFlag==true || this.breakOut==true) continue;

    this.clearNoteBuffer();
    this.hasChangedFlag=false;
    this.solveMethodF3(6,64);
    if(this.hasChangedFlag==true || this.breakOut==true) continue;

    this.clearNoteBuffer();
  }
  this.echoNotes();
}


Sudoku.prototype.ariadnesThread=function()
{
  var x,y,n,val,tempSolvedCount,savedMatrix,solvedAtAll;

  this.logicSolve();
  if(this.solvedCount==81)
  {
    return true;
  }

  //find the first cell with more than one option..

  found=false;
  for(x=0;x<9;x++)
  {
    for(y=0;y<9;y++)
    {
      if(this.matrix[y][x].length>1)
      {
        found=true;
        break;
      }
    }
    if(found==true) break;
  }
  if(found==false) return false;

  this.addNote("<br><b>"+mlText.endLogic+"</b></br>");
  this.statusNote();

  //save current status
  tempSolvedCount=this.solvedCount;
  savedMatrix=this.getMatrixString();

  solvedAtAll=false;

  for(n=0;n<this.matrix[y][x].length;n++)
  {
    val=this.matrix[y][x].charAt(n);
    this.addNote("<br><b>"+mlText.guessing+"</b><br>",{val:val,cell:this.cellString(x,y)});
    this.statusNote();
    try
    {
      this.difficultyScore+=1000;
      this.guesses++;
      this.set(x,y,val,true);
      solved=this.ariadnesThread();
    }
    catch (e)
    {
      //invalid solution
      this.addNote(e);
      solved=false;
    }

    solvedAtAll|=solved;

    if(solved)
    {
      this.addNote("<br><b>"+mlText.guessingSucceeded+"</b><br>",{val:val,cell:this.cellString(x,y)});
    }
    else
    {
      this.addNote("<br><b>"+mlText.guessingFailed+"</b><br>",{val:val,cell:this.cellString(x,y)});
    }
    if(solved && this.returnFirstAnswer) return true;
    if(solved && this.solutions>=2 && this.stopAfterTwoSolutions) return true;

    //otherwise continue
    //return to saved status
    this.solvedCount=tempSolvedCount;
    this.setMatrixString(savedMatrix);
  }
  this.addNote("<br><b>"+mlText.endOfAriadne+"</b></br>");
  return solvedAtAll;
}


Sudoku.prototype.solveStartGrid=function()
{
  shading1="#C0C0C0";
  this.step=false;
  this.breakOut=false;
  this.solutions=0;
  this.resetWorkingGrid();
  this.hasChangedFlag=false;
  this.runStartGrid();
  this.echoNotes();
}


Sudoku.prototype.solveBySteps=function()
{
  shading1="#C0C0C0";
  this.step=true;
  this.breakOut=false;

  this.hasChangedFlag=false;
  this.runStartGrid();
  this.logicSolve(); //can't do ariadne's thread if solving by steps
  if(this.breakOut==true) this.addNote(mlText.stepSolveCancelled);
  if(this.solvedCount==81)
  {
    this.addNote(mlText.checkingGridValid);
    this.statusNote();
    if(this.checkSolution()!=true)
    {
      this.addNote(mlText.invalidSolution);
    }
    else
    {
      this.addNote(mlText.validSolution);
      if(this.doAlert) alert(mlText.validSolution);
    }
  }
  else if(this.breakOut==false)
  {
    this.addNote(mlText.couldNotSolveBySteps);
    if(this.doAlert) alert(mlText.couldNotSolveBySteps);
  }
  this.echoNotes();
  this.refreshWorkingGrid();
}

Sudoku.prototype.suggestAMove=function()
{
  shading1="#C0C0C0";
  this.solveStartGrid();
  this.solveBySteps();
}

Sudoku.prototype.solveFromScratch=function()
{
  this.step=false;
  this.breakOut=false;
  var startTime=new Date();

  if(document.getElementById("ariadneCheckBox")) this.doAriadne=document.getElementById("ariadneCheckBox").checked;
  if(document.getElementById("returnFirstAnswerCheckBox")) this.returnFirstAnswer=document.getElementById("returnFirstAnswerCheckBox").checked;

  var ss0=getSudokuString("x");

  saveCurrentGrid(); //if possible

  this.solutions=0;
  var trySubmit=false;
  try
  {
    this.resetWorkingGrid();
    this.hasChangedFlag=false;
    this.runStartGrid();
    if(this.doAriadne)
    {
      this.ariadnesThread();
    }
    else
    {
      this.logicSolve();
    }
    this.refreshWorkingGrid();
    var endTime=new Date()
    var elapsedTime=endTime.getTime()-startTime.getTime();
    this.addNote(mlText.timeElapsed,{secs:(elapsedTime/1000)});
    this.echoNotes();

    if(this.solutions>0)
    {
      this.setMatrixString(this.latestSolution);
      this.refreshWorkingGrid();
      if(this.solutions==1 && this.guesses==0 )
      {
        if(this.doAlert) alert(mlText.solvedByLogicOnly);
        trySubmit=true;
      }
      else if(this.solutions==1 && this.guesses>0 && !this.returnFirstAnswer)
      {
        if(this.doAlert) alert(mlText.guessedBut1Solution);
        trySubmit=true;
      }
      else if(this.solutions==1 && this.guesses>0 && this.returnFirstAnswer)
      {
        if(this.doAlert) alert(mlText.guessedMaybeMoreThan1Solution);
      }
      else if(this.solutions==2 && this.stopAfterTwoSolutions)
      {
        if(this.doAlert) alert(mlText.solvedButMoreThan1Solution);
        trySubmit=true;
      }
      else
      {
        if(this.doAlert) alert(this.parseString(mlText.solvedButNSolutions,{solutions:this.solutions}));
      }
    }
    else
    {
      if(this.doAriadne)
      {
        if(this.doAlert) alert(mlText.didntSolve+"\n"+mlText.noSolution);
      }
      else
      {
        if(this.doAlert) alert(mlText.didntSolve+"\n"+mlText.noSolveOptions);
      }
    }
  }
  catch (e)
  {
    this.echoNotes();
    this.refreshWorkingGrid();
    if(this.doAlert) alert(e);
  }

  if(trySubmit && this.lastSubmittedGrid!=ss0)
  {
    this.addNote(mlText.submittingGrid);
    this.echoNotes();
    submitGrid(this.difficultyScore,this.guesses,this.solutions);
    this.lastSubmittedGrid=ss0;
  }
}



/////////////////////////////////////////////////////////////////////////////////////////////////
//
//
//  SUDOKU SOLVE METHODS
//
/////////////////////////////////////////////////////////////////////////////////////////////////




Sudoku.prototype.solveMethodA=function()
{
/*
Look across a row in the solution grid to see if there are any numbers that occur only once in the row.
If so, the cell containing that occurance must be the solution. This rule is repeated for columns and blocks.
*/
  var x,y,bx,by,n, foundOne;

  this.startMethodNote("A");

  do
  {
    foundOne=false;
    for(n=1;n<=9;n++)
    {
      for(x=0;x<9;x++)
      {
        if(this.columnCount(x,n)==1 && this.matrix[this.lastFoundY][x]!=n)
        {
          this.addNote(mlText.methodA_column,{col:this.xName[x],val:n,row:this.yName[this.lastFoundY]});
          if(this.step) this.explainAndPause(new Array(new Array('col',x,'#98FB98'),new Array('cell',x,this.lastFoundY,'#FFD700')));
          this.difficultyScore+=4;
          this.set(x,this.lastFoundY,n,true);
          foundOne=true;
          if(this.breakOut==true) return this.endMethodNote("A");
        }
      }
      for(y=0;y<9;y++)
      {
        if(this.rowCount(y,n)==1 && this.matrix[y][this.lastFoundX]!=n)
        {
          this.addNote(mlText.methodA_row,{row:this.yName[y],val:n,col:this.xName[this.lastFoundX]});
          if(this.step) this.explainAndPause(new Array(new Array('row',y,'#98FB98'),new Array('cell',this.lastFoundX,y,'#FFD700')));
          this.difficultyScore+=4;
          this.set(this.lastFoundX,y,n,true);
          foundOne=true;
          if(this.breakOut==true) return this.endMethodNote("A");
        }
      }
      for(bx=0;bx<3;bx++)
      {
        for(by=0;by<3;by++)
        {
          if(this.blockCount(bx,by,n)==1 && this.matrix[this.lastFoundY][this.lastFoundX]!=n)
          {
            this.addNote(mlText.methodA_block,{block:this.cellString(bx*3,by*3),val:n,cell:this.cellString(this.lastFoundX,this.lastFoundY)});
            if(this.step) this.explainAndPause(new Array(new Array('block',bx*3,by*3,'#98FB98'),new Array('cell',this.lastFoundX,this.lastFoundY,'#FFD700')));
            this.difficultyScore+=4;
            this.set(this.lastFoundX,this.lastFoundY,n,true);
            foundOne=true;
            if(this.breakOut==true) return this.endMethodNote("A");
          }
        }
      }
    }
  } while(foundOne==true && this.breakOut==false)
  this.endMethodNote("A");
}



Sudoku.prototype.solveMethodB=function()
{
/*
Look at a row in the solution grid to see if there are any numbers that occur only in a specific block.
That number must be in that row, so eliminate that number from other cells in the block. Repeat for columns.

The same the other way round - look at a block in the solution grid to see if there are any numbers in it
that occur only in a specific row or column. That number must be in that block, so eliminate the number from
cells in the row or column outside the block.
*/

  var x,y,bx,by,sx,sy,i,n, foundOne,b0,b1,b2,bix;
  var c,cc;
  var allSameRow,allSameCol;

  this.startMethodNote("B");

  do
  {
    foundOne=false;
    //for each column
    for(x=0;x<9;x++)
    {
      //for each number
      for(n=1;n<=9;n++)
      {
        //are there up to 3 of that number found in that column, could be that the rule works.
        cc=this.columnCount(x,n);
        if(cc<=3 && cc>1)
        {
          //but need to check all in the same block
          //set block flags - 1=not found, 2=found
          b0=1;b1=1;b2=1;
          //go through each found element, and set the block flag it is found in
          for(i=0;i<this.found.length;i++)
          {
            bix=this.found[i][1];
            if(bix<=2) b0=2;
            else if(bix>=6) b2=2;
            else b1=2;
          }
          //if they are all in one block, the flags multiplied together will make 2
          if(b0*b1*b2==2)
          {
            bx=3*parseInt(x/3);
            //work out the start y-coord of the block they're in using some maths
            by=b1*3+b2*6-9;
            //if there's more than 'cc' numbers in the block, the rule has worked.

            if(this.blockCount(bx/3,by/3,n)>cc)
            {
              foundOne=true;
              this.addNote(mlText.methodB_block_col,{val:n,block:this.cellString(bx,by),col:this.xName[x]});
              if(this.step) this.explainAndPause(new Array(new Array('block',bx,by,'#8470FF'),new Array('col',x,'#98FB98'),new Array('cell',x,by,'pink'),new Array('cell',x,by+1,'pink'),new Array('cell',x,by+2,'pink')));
              for(i=0;i<this.found.length;i++)
              {
                if(this.found[i][0]!=x)
                {
                  this.difficultyScore+=8;
                  this.remove(this.found[i][0],this.found[i][1],n);
                }
              }
              if(this.breakOut==true) return this.endMethodNote("B");
            }
          }
        }
      }
    }
    for(y=0;y<9;y++)
    {
      for(n=1;n<=9;n++)
      {
        cc=this.rowCount(y,n);
        if(cc<=3 && cc>1)
        {
          b0=1;b1=1;b2=1;
          for(i=0;i<this.found.length;i++)
          {
            bix=this.found[i][0];
            if(bix<=2) b0=2;
            else if(bix>=6) b2=2;
            else b1=2;
          }
          if(b0*b1*b2==2)
          {
            by=3*parseInt(y/3);
            bx=b1*3+b2*6-9;
            if(this.blockCount(bx/3,by/3,n)>cc)
            {
              foundOne=true;
              this.addNote(mlText.methodB_block_row,{val:n,block:this.cellString(bx,by),row:this.yName[y]});
              if(this.step) this.explainAndPause(new Array(new Array('block',bx,by,'#8470FF'),new Array('row',y,'#98FB98'),new Array('cell',bx,y,'pink'),new Array('cell',bx+1,y,'pink'),new Array('cell',bx+2,y,'pink')));
              for(i=0;i<this.found.length;i++)
              {
                if(this.found[i][1]!=y)
                {
                  this.difficultyScore+=8;
                  this.remove(this.found[i][0],this.found[i][1],n);
                }
              }
              if(this.breakOut==true) return this.endMethodNote("B");
            }
          }
        }
      }
    }
    for(bx=0;bx<3;bx++)
    {
      for(by=0;by<3;by++)
      {
        //for each number
        for(n=1;n<=9;n++)
        {
          //are there up to 3 of that number found in that block, could be that the rule works.
          cc=this.blockCount(bx,by,n);
          if(cc<=3 && cc>1)
          {
            //but need to check either (a) all in the same row or (b) all in the same column
            //[but they can't be both!]
            allSameRow=true;
            allSameCol=true;
            for(i=1;i<this.found.length;i++)
            {
              if(this.found[0][1]!=this.found[i][1]) allSameRow=false;
              if(this.found[0][0]!=this.found[i][0]) allSameCol=false;
            }

            if(allSameRow)
            {
              //are there other cells in the row with this number lurking outside the block
              if(this.rowCount(this.found[0][1],n)>cc)
              {
                foundOne=true;
                this.addNote(mlText.methodB_row_block,{val:n,row:this.yName[this.found[0][1]],block:this.cellString(bx*3,by*3)});
                if(this.step) this.explainAndPause(new Array(new Array('block',bx*3,by*3,'#8470FF'),new Array('row',this.found[0][1],'#98FB98'),new Array('cell',bx*3,this.found[0][1],'pink'),new Array('cell',bx*3+1,this.found[0][1],'pink'),new Array('cell',bx*3+2,this.found[0][1],'pink')));
                for(i=0;i<this.found.length;i++)
                {
                  if(this.found[i][0]<bx*3 || this.found[i][0]>2+bx*3)
                  {
                    this.difficultyScore+=8;
                    this.remove(this.found[i][0],this.found[i][1],n);
                  }
                }
                if(this.breakOut==true) return this.endMethodNote("B");
              }
            }

            if(allSameCol)
            {
              if(this.columnCount(this.found[0][0],n)>cc)
              {
                foundOne=true;
                this.addNote(mlText.methodB_col_block,{val:n,col:this.xName[this.found[0][0]],block:this.cellString(bx*3,by*3)});
                if(this.step) this.explainAndPause(new Array(new Array('block',bx*3,by*3,'#8470FF'),new Array('col',this.found[0][0],'#98FB98'),new Array('cell',this.found[0][0],by*3,'pink'),new Array('cell',this.found[0][0],by*3+1,'pink'),new Array('cell',this.found[0][0],by*3+2,'pink')));
                for(i=0;i<this.found.length;i++)
                {
                  if(this.found[i][1]<by*3 || this.found[i][1]>2+by*3)
                  {
                    this.difficultyScore+=8;
                    this.remove(this.found[i][0],this.found[i][1],n);
                  }
                }
                if(this.breakOut==true) return this.endMethodNote("B");
              }
            }
          }
        }
      }
    }

  } while(foundOne==true)
  this.endMethodNote("B");
}










Sudoku.prototype.solveMethodC=function(c)
{
/*
Look at a row in the solution grid to see if there is a number that occurs only twice in the row.
If the cells they occur in match identically with another number that satisfies this criterion,
then those cells must contain that number pair - so eliminate the other options in those cells.
Again, this is repeated for columns and blocks. This method is also repeated for triplets and upwards.
*/
  var x,y,bx,by,n, foundOne,foundCountOf;

  this.startMethodNote("C");

  do
  {
    foundOne=false;
    for(x=0;x<9;x++)
    {
      foundCountOf=null;
      foundCountOf=new Array();
      for(n=1;n<=9;n++)
      {
        if(this.columnCount(x,n)==c)
        {
          //this.addNote("Found "+c+" counts of "+n+" in column "+this.xName[x]);
          foundCountOf.push(new Array(n,this.found.copyOf()));
        }
      }
      foundOne|=this.findUnique(foundCountOf,c)
      if(this.breakOut==true) return this.endMethodNote("C");
    }
    for(y=0;y<9;y++)
    {
      foundCountOf=null;
      foundCountOf=new Array();
      for(n=1;n<=9;n++)
      {
        if(this.rowCount(y,n)==c)
        {
          //this.addNote("Found "+c+" counts of "+n+" in row "+y);
          foundCountOf.push(new Array(n,this.found.copyOf()));
        }
      }
      foundOne|=this.findUnique(foundCountOf,c)
      if(this.breakOut==true) return this.endMethodNote("C");
    }
    for(bx=0;bx<3;bx++)
    {
      for(by=0;by<3;by++)
      {
        foundCountOf=null;
        foundCountOf=new Array();
        for(n=1;n<=9;n++)
        {
          if(this.blockCount(bx,by,n)==c)
          {
            //this.addNote("Found "+c+" counts of "+n+" in block ["+this.xName[bx*3]+(by*3)+"]");
            foundCountOf.push(new Array(n,this.found.copyOf()));
          }
        }
        foundOne|=this.findUnique(foundCountOf,c)
        if(this.breakOut==true) return this.endMethodNote("C");
      }
    }
  } while(foundOne==true)
  return this.endMethodNote("C");
}




/*
SuDoku Solver by Logic v1.21
Copyright (C) Peter Wake 2005

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

The GNU General Public License can be seen at
  http://www.gnu.org/licenses/gpl.html

Or contact the author via the website link at
  http://www.sudokusolver.co.uk
*/


//=============================================================================
// Contributors
// ------------
// ATC - Alan Chambers (alpha tango charlie at delcam dot com)
//-----------------------------------------------------------------------------


//=============================================================================
// These arrays of unit indices are used so often in the code that it is
// inefficent to create them over and over again. It would bwe useful to
// make one of these objects a member of Sudoku, but it is used only in
// Method D2 for now.
//-----------------------------------------------------------------------------
// History
// Who When     What
// --- -------- ---------------------------------------------------------------
// ATC 06/09/05 Written.
//-----------------------------------------------------------------------------
function CellArrays()
{
  this.ROW_INDICES = new Array(9)
  this.ROW_INDICES[0] = new Array( 0,  1,  2,  3,  4,  5,  6,  7,  8);
  this.ROW_INDICES[1] = new Array( 9, 10, 11, 12, 13, 14, 15, 16, 17);
  this.ROW_INDICES[2] = new Array(18, 19, 20, 21, 22, 23, 24, 25, 26);
  this.ROW_INDICES[3] = new Array(27, 28, 29, 30, 31, 32, 33, 34, 35);
  this.ROW_INDICES[4] = new Array(36, 37, 38, 39, 40, 41, 42, 43, 44);
  this.ROW_INDICES[5] = new Array(45, 46, 47, 48, 49, 50, 51, 52, 53);
  this.ROW_INDICES[6] = new Array(54, 55, 56, 57, 58, 59, 60, 61, 62);
  this.ROW_INDICES[7] = new Array(63, 64, 65, 66, 67, 68, 69, 70, 71);
  this.ROW_INDICES[8] = new Array(72, 73, 74, 75, 76, 77, 78, 79, 80);

  this.COLUMN_INDICES = new Array(9);
  this.COLUMN_INDICES[0] = new Array( 0,  9, 18, 27, 36, 45, 54, 63, 72);
  this.COLUMN_INDICES[1] = new Array( 1, 10, 19, 28, 37, 46, 55, 64, 73);
  this.COLUMN_INDICES[2] = new Array( 2, 11, 20, 29, 38, 47, 56, 65, 74);
  this.COLUMN_INDICES[3] = new Array( 3, 12, 21, 30, 39, 48, 57, 66, 75);
  this.COLUMN_INDICES[4] = new Array( 4, 13, 22, 31, 40, 49, 58, 67, 76);
  this.COLUMN_INDICES[5] = new Array( 5, 14, 23, 32, 41, 50, 59, 68, 77);
  this.COLUMN_INDICES[6] = new Array( 6, 15, 24, 33, 42, 51, 60, 69, 78);
  this.COLUMN_INDICES[7] = new Array( 7, 16, 25, 34, 43, 52, 61, 70, 79);
  this.COLUMN_INDICES[8] = new Array( 8, 17, 26, 35, 44, 53, 62, 71, 80);

  this.BLOCK_INDICES = new Array(9);
  this.BLOCK_INDICES[0] = new Array( 0,  1,  2,  9, 10, 11, 18, 19, 20);
  this.BLOCK_INDICES[1] = new Array( 3,  4,  5, 12, 13, 14, 21, 22, 23);
  this.BLOCK_INDICES[2] = new Array( 6,  7,  8, 15, 16, 17, 24, 25, 26);
  this.BLOCK_INDICES[3] = new Array(27, 28, 29, 36, 37, 38, 45, 46, 47);
  this.BLOCK_INDICES[4] = new Array(30, 31, 32, 39, 40, 41, 48, 49, 50);
  this.BLOCK_INDICES[5] = new Array(33, 34, 35, 42, 43, 44, 51, 52, 53);
  this.BLOCK_INDICES[6] = new Array(54, 55, 56, 63, 64, 65, 72, 73, 74);
  this.BLOCK_INDICES[7] = new Array(57, 58, 59, 66, 67, 68, 75, 76, 77);
  this.BLOCK_INDICES[8] = new Array(60, 61, 62, 69, 70, 71, 78, 79, 80);
}


//=============================================================================
// This object allows us to iterate over a set of indices a bit like this:
//
//   for (int i = 0; i < range; ++i)
//     for (int j = i + 1; j < range; ++j)
//       for (int k = j + 1; k < range; ++k)
//         ...
//
// but with an arbitrary number of counters. This is useful for the generic
// subset solvers.
//-----------------------------------------------------------------------------
// History
// Who When     What
// --- -------- ---------------------------------------------------------------
// ATC 01/09/05 Written.
// ATC 06/09/05 Ported to JavaScript.
//-----------------------------------------------------------------------------
function VectorIterator(size, range)
{
  this.range   = range;
  this.indices = new Array();

  for (var i = 0; i < size; ++i)
  {
    this.indices[i] = i;
  }
}


//=============================================================================
// History
// Who When     What
// --- -------- ---------------------------------------------------------------
// ATC 01/09/05 Written.
// ATC 06/09/05 Ported to JavaScript.
//-----------------------------------------------------------------------------
VectorIterator.prototype.increment = function()
{
  var size = this.indices.length;

  while (true)
  {
    // Start with the last (i.e. most nested) index. If it can be incremnted
    // without exceeding the range, we are done. Otherwise increment the next
    // least nested index and reset the last one (and so on). The range for
    // each index is one less than for the next more nested one.
    for (var i = size - 1; i >= 0; --i)
    {
      ++this.indices[i];
      for (var j = i + 1; j < size; ++j)
        this.indices[j] = this.indices[j - 1] + 1;

      if (this.indices[i] < this.range + i + 1 - size)
        return true;
    }

    // Finally we can go no further. The iterator is finished.
    if (this.indices[0] >= this.range + 1 - size)
      return false;
  }
}


//=============================================================================
// This struct is used to keep track of which subsets are currently in play
// when making union calculations.
//-----------------------------------------------------------------------------
// History
// Who When     What
// --- -------- ---------------------------------------------------------------
// ATC 01/09/05 Written.
// ATC 06/09/05 Ported to JavaScript.
//-----------------------------------------------------------------------------
function Subset()
{
  this.reference = 0;
  this.items     = new Array();
}


//=============================================================================
// Create the union of a collection of arrays of numbers. For example:
// {13} {125} {23} would result in {1235}.
//-----------------------------------------------------------------------------
// History
// Who When     What
// --- -------- ---------------------------------------------------------------
// ATC 01/09/05 Written.
// ATC 06/09/05 Ported to JavaScript.
//-----------------------------------------------------------------------------
function createUnionOfSubsets(iter, subsets, items, references)
{
  var size = iter.indices.length;

  for (var i = 0; i < size; ++i)
  {
    var index = iter.indices[i];
    var subset = subsets[index];
    references.push(subset.reference);

    for (var j = 0; j < subset.items.length; ++j)
    {
      // Check to see if the item already exists in the union.
      var already_present = false;
      for (var k = 0; k < items.length; ++k)
      {
        if (items[k] == subset.items[j])
        {
          already_present = true;
          break;
        }
      }

      // Add the item to the union.
      if (!already_present)
        items.push(subset.items[j]);
    }
  }

  // Candidate lists are always assumed to be sorted.
  items.sort();

  return items.length;
}


//=============================================================================
// Convert the cell's candidate string into an array of digits. My C++ version
// works in terms of vector<int>, rather than strings of digits, so I have added
// this make porting my algorithm simpler.
//-----------------------------------------------------------------------------
// History
// Who When     What
// --- -------- ---------------------------------------------------------------
// ATC 01/09/05 Written.
// ATC 06/09/05 Ported to JavaScript.
//-----------------------------------------------------------------------------
Sudoku.prototype.getCandidates = function(cell, candidates)
{
  var row = Math.floor(cell/9);
  var col = cell%9;

  for (var candidate = 1; candidate <= 9; ++candidate)
  {
    if (this.matrix[row][col].indexOf(candidate) >= 0)
      candidates.push(candidate);
  }

  return candidates.length;
}


//=============================================================================
// History
// Who When     What
// --- -------- ---------------------------------------------------------------
// ATC 01/09/05 Written.
// ATC 06/09/05 Ported to JavaScript.
//-----------------------------------------------------------------------------
Sudoku.prototype.solveMethodD2 = function(size, score)
{
  this.startMethodNote(mlText.methodD_name);

  var cells = new CellArrays();

  this.addNote("");
  this.addNote(mlText.methodD_info,{size:size});

  {
    var removed = 0;
    this.addNote(mlText.methodD_check_col);

    for (var unit = 0; unit < 9 && !this.breakOut; ++unit)
    {
      var name = this.parseString(mlText.column,{col:this.xName[unit]});
      removed += this.solveSubsetsByCandidate(cells.COLUMN_INDICES[unit], size, name, score, new Array('col',unit,'#8470FF'));
    }

  }

  {
    var removed = 0;
    this.addNote(mlText.methodD_check_row);

    for (var unit = 0; unit < 9 && !this.breakOut; ++unit)
    {
      var name = this.parseString(mlText.row,{row:this.yName[unit]});
      this.solveSubsetsByCandidate(cells.ROW_INDICES[unit], size, name, score, new Array('row',unit,'#8470FF'));
    }

  }

  {
    var removed = 0;
    this.addNote(mlText.methodD_check_block);

    for (var unit = 0; unit < 9 && !this.breakOut; ++unit)
    {
      var row = Math.floor(cells.BLOCK_INDICES[unit][0]/9);
      var col = cells.BLOCK_INDICES[unit][0]%9;
      var name = this.parseString(mlText.block,{block:this.cellString(col,row)});
      this.solveSubsetsByCandidate(cells.BLOCK_INDICES[unit], size, name, score, new Array('block',col,row,'#8470FF'));
    }

  }

  // Interface to existing reporting. Ideally push this back to the highest
  // level. Create a new blank report here only in Method D is called again.

  this.addNote("");
  this.endMethodNote("D");
}


//=============================================================================
// Generic implementation for finding disjoint subsets. For example, if we have
// {12} {13} {123}, then no other cells in the unit can have candidates 1, 2 or 3.
//-----------------------------------------------------------------------------
// Parameters:
// cells       - an array of the indices of cells in the unit being tested (index
//               of a cell is row*9+col, row and col are zero-based).
// subset_size - the size of subset to look for.
//-----------------------------------------------------------------------------
// History
// Who When     What
// --- -------- ---------------------------------------------------------------
// ATC 01/09/05 Written.
// ATC 06/09/05 Ported to JavaScript.
//-----------------------------------------------------------------------------
Sudoku.prototype.solveSubsetsByCandidate = function(cells, subsetSize, name, score, baseHighlightEl)
{
  var highlightArray;

  // Find all subsets of subsetSize or less candidates. Ignore singletons
  // (cells which are solved already).
  var subsets = new Array();
  for (var index = 0; index < 9; ++index)
  {
    var subset = new Subset;
    var size = this.getCandidates(cells[index], subset.items);
    if (size > 1 && size <= subsetSize)
    {
      subset.reference = index;
      subsets.push(subset);
    }
  }

  // We need at least N subsets or we can't do the union calculations.
  if (subsets.length < subsetSize)
    return 0;

  // This iterates over all the possible combinations of indices for making
  // unions. We make a union of each group of subsetSize subsets.
  var removedTotal = 0;
  var iter = new VectorIterator(subsetSize, subsets.length);
  do
  {
    // Items in the union of N subsets.
    var items = new Array();
    // References for the N subsets in the union. We'll want this later.
    var references = new Array();
    // Does the union of subsets have the right size?
    if (createUnionOfSubsets(iter, subsets, items, references) == subsetSize)
    {
      // Describe what we have found in the output.
      var chain = " ";
      if(this.step) highlightArray=new Array(baseHighlightEl);

      for (var i = 0; i < references.length; ++i)
      {
        var cell = cells[references[i]];
        var row = Math.floor(cell/9);
        var col = cell%9;
        chain = chain + " " + this.cellString(col,row) + " ";
        if(this.step) highlightArray.push(new Array('cell',col,row,'#98FB98'));
      }
      this.addNote(mlText.methodD2_found,{name:name,items:items.join(),chain:chain});


      // Loop over all the cells in the unit, skipping the ones whose subsets were used
      // in the union, and reset the items in the subset as candidates.
      var removed = 0;

      for (var index = 0; index < 9; ++index)
      {
        // There must be an easier way!
        var reset_allowed = true;
        for (var i = 0; i < references.length; ++i)
        {
          if (references[i] == index)
          {
            reset_allowed = false;
            break;
          }
        }

        // This is quite clunky, but a lot of the code is geared around creating some
        // reasonable trace output similar to the other Method D implementation.
        if (reset_allowed)
        {
          for (var j = 0; j < items.length; ++j)
          {
            var row = Math.floor(cells[index]/9);
            var col = cells[index]%9;

            if (this.isValAtXY(col, row, items[j]))
            {
              this.addNote(mlText.methodD2_removing,{item:items[j],cell:this.cellString(col,row)});

              if(this.step)
              {
                highlightArray.push(new Array('cell',col,row,'pink'));
                this.explainAndPause(highlightArray);
                highlightArray.pop();
              }

              this.remove(col, row, items[j]);
              ++removed;
            }
          }
        }
      }

      if (removed > 0)
      {
        this.difficultyScore += score;
        removedTotal         += removed;
      }
      else
      {
        this.addNote(mlText.methodD2_nothing_removed);
      }
    }
  }
  while (iter.increment() && !this.breakOut);

  return removedTotal;
}





//=============================================================================
// History
// Who When     What
// --- -------- ---------------------------------------------------------------
// ATC 15/09/05 Written.
//-----------------------------------------------------------------------------
function BlockArrays()
{
  this.BLOCK_ROW_INDICES = new Array(9);
  this.BLOCK_ROW_INDICES[0] = new Array(0, 1, 2);
  this.BLOCK_ROW_INDICES[1] = new Array(1, 2, 0);
  this.BLOCK_ROW_INDICES[2] = new Array(2, 0, 1);
  this.BLOCK_ROW_INDICES[3] = new Array(3, 4, 5);
  this.BLOCK_ROW_INDICES[4] = new Array(4, 5, 3);
  this.BLOCK_ROW_INDICES[5] = new Array(5, 3, 4);
  this.BLOCK_ROW_INDICES[6] = new Array(6, 7, 8);
  this.BLOCK_ROW_INDICES[7] = new Array(7, 8, 6);
  this.BLOCK_ROW_INDICES[8] = new Array(8, 6, 7);

  this.BLOCK_COLUMN_INDICES = new Array(9);
  this.BLOCK_COLUMN_INDICES[0] = new Array(0, 3, 6);
  this.BLOCK_COLUMN_INDICES[1] = new Array(3, 6, 0);
  this.BLOCK_COLUMN_INDICES[2] = new Array(6, 0, 3);
  this.BLOCK_COLUMN_INDICES[3] = new Array(1, 4, 7);
  this.BLOCK_COLUMN_INDICES[4] = new Array(4, 7, 1);
  this.BLOCK_COLUMN_INDICES[5] = new Array(7, 1, 4);
  this.BLOCK_COLUMN_INDICES[6] = new Array(2, 5, 8);
  this.BLOCK_COLUMN_INDICES[7] = new Array(5, 8, 2);
  this.BLOCK_COLUMN_INDICES[8] = new Array(8, 2, 4);
}


//=============================================================================
// Find which rows or columns overlapping a particular block contain a given
// candidate.
//-----------------------------------------------------------------------------
// History
// Who When     What
// --- -------- ---------------------------------------------------------------
// ATC 01/09/05 Written.
// ATC 16/09/05 Ported to JavaScript.
//-----------------------------------------------------------------------------
Sudoku.prototype.getUnitIndicesInBlock = function(block, candidate, calc, units)
{
  var indices = new Array();
  this.getIndicesInUnit(block, candidate, indices);

  for (var i = 0; i < indices.length; ++i)
  {
    var unit = calc.func(block[indices[i]]);
    if (!arrayContains(units, unit))
    {
      units.push(unit);
    }
  }

  units.sort();

  return units.length;
}


//=============================================================================
// History
// Who When     What
// --- -------- ---------------------------------------------------------------
// ATC 01/09/05 Written.
// ATC 16/09/05 Ported to JavaScript.
//-----------------------------------------------------------------------------
Sudoku.prototype.getIndicesInUnit = function(cells, candidate, indices)
{
  for (var i = 0; i < 9; ++i)
  {
    var cell = cells[i];
    var row  = Math.floor(cell/9);
    var col  = cell%9;

    if (this.matrix[row][col].indexOf(candidate) >= 0)
      indices.push(i);
  }

  return indices.length;
}


//=============================================================================
// History
// Who When     What
// --- -------- ---------------------------------------------------------------
// ATC 13/09/05 Written.
//-----------------------------------------------------------------------------
function arrayContains(container, value)
{
  var result = false;

  for (var i = 0; i < container.length; ++i)
  {
    if (container[i] == value)
    {
      result = true;
      break;
    }
  }

  return result
}


//=============================================================================
// History
// Who When     What
// --- -------- ---------------------------------------------------------------
// ATC 02/09/05 Written.
// ATC 13/09/05 Ported to JavaScript.
//-----------------------------------------------------------------------------
Sudoku.prototype.solveMethodF3 = function(size,score)
{
  switch (size)
  {
    case 2: this.startMethodNote(mlText.methodF3_name2); break;
    case 3: this.startMethodNote(mlText.methodF3_name3); break;
    case 4: this.startMethodNote(mlText.methodF3_name4); break;
    case 5: this.startMethodNote(mlText.methodF3_name5); break;
    default: this.startMethodNote(this.parseString(mlText.methodF3_nameN,{n:size}));
  }

  this.cells = new CellArrays();
  var removed=0;

  for (var candidate = 1; candidate <= 9  && !this.breakOut; ++candidate)
  {
    removed+=this.solveNxNSubgridsImpl(this.cells.COLUMN_INDICES, candidate, size, 1, score);
  }
  for (var candidate = 1; candidate <= 9 && !this.breakOut; ++candidate)
  {
    removed+=this.solveNxNSubgridsImpl(this.cells.ROW_INDICES, candidate, size, 0, score);
  }
  if (size == 2)
  {
    removed+=this.solveBlocksWithSharedUnits(score);
  }

  this.endMethodNote("F");
}


//=============================================================================
//      ABC DEF GHI
//      --- --- ---
//   1 |   |   |   |
//   2 |o o| o |   |
//   3 |   |   |   |
//      --- --- ---
//   4 |   |   |   |
//   5 |o o|   |   |
//   6 |o  | o |   |
//      --- --- ---
//
// The candidate X occurs in a maximum of N rows (3 in the example). There are
// N columns for which this is true, with the same N rows in each case (here
// columns A, C and E). These mark out an NxN subgrid which have X in all the columns
// and all the rows in some order or other. This means X can be removed as a
// candidate from the same rows in all other columns. There is a similar rule
// with rows and columns swapped.
//-----------------------------------------------------------------------------
// History
// Who When     What
// --- -------- ---------------------------------------------------------------
// ATC 01/09/05 Written.
// ATC 13/09/05 Ported to JavaScript.
//-----------------------------------------------------------------------------
Sudoku.prototype.solveNxNSubgridsImpl = function(cells, candidate, subsetSize, type, score)
{
  var subsets = new Array();
  var totalRemoved=0;
  for (var unit = 0; unit < 9; ++unit)
  {
    var subset = new Subset;
    // Is this valid: the candidate can appear in up to N cells in the unit? I
    // think it is, but might need to spend more time thinking about it.
    var size = this.getIndicesInUnit(cells[unit], candidate, subset.items);
    if (size > 1 && size <= subsetSize)
    {
      subset.reference = unit;
      subsets.push(subset);
    }
  }

  // We need at least N subsets or we can't do the union calculations.
  if (subsets.length < subsetSize)
    return 0;

  // This iterates over all the possible combinations of indices for making
  // unions. We make a union of each group of N subsets.
  var iter = new VectorIterator(subsetSize, subsets.length);
  do
  {
    // Indices of rows or columns at which the candidate occurs.
    var indices = new Array();
    // Rows or columns in which candidate occurs only N times.
    var units = new Array();
    // Does the union of subsets have the right size?
    var highlightArray = [];
    var removed=0;
    
    if (createUnionOfSubsets(iter, subsets, indices, units) == subsetSize)
    {
      var row_chain = " ";
      var row_name = (type == 1) ? mlText.columns : mlText.rows;
      for (var i = 0; i < units.length; ++i)
        row_chain = row_chain + "[" + ((type == 0) ? this.yName[units[i]] : this.xName[units[i]]) + "] ";

      var col_chain = " ";
      var col_name = (type == 0) ? mlText.columns : mlText.rows;
      for (var i = 0; i < indices.length; ++i)
        col_chain = col_chain + "[" + ((type == 1) ? this.yName[indices[i]] : this.xName[indices[i]]) + "] ";

      for (var i = 0; i < units.length; ++i)
      {
        for (var j = 0; j < indices.length; ++j)
        {
          if(type==0) highlightArray.push(new Array('cell',indices[j],units[i],'#98FB98'));
          else highlightArray.push(new Array('cell',units[i],indices[j],'#98FB98'));
        }
      }

      this.addNote(mlText.methodF3_found,{val:candidate,row_name:row_name,row_chain:row_chain,col_name:col_name,col_chain:col_chain});


      // Loop over all the units, skipping the ones whose subsets were used in the
      // union, and reset the provided value as a candidate.
      for (var unit = 0; unit < 9; ++unit)
      {
        if (!arrayContains(units, unit))
        {
          for (var i = 0; i < subsetSize; ++i)
          {
            var index = indices[i];
            removed+=this.removeSubgridCandidate(cells[unit][index], candidate, highlightArray);
          }
        }
      }

      // Special extension for X-Wing
      if (subsetSize == 2)
      {
        var unit1 = units[0];
        var unit2 = units[1];

        // If unit1 and unit2 are in the same block row/column, reset candidate in all
        // other cells in the two affected blocks. This is a bonus add-on, in a way, and
        // implements part of the additional requirements for Method F. Not sure how to
        // extend this to 3x3 and larger grids - probably some reason why it won't work.
        if (Math.floor(unit1/3) == Math.floor(unit2/3))
        {
          removed+=this.clearCandidateFromBlock(cells,
            cells[unit1][indices[0]],
            cells[unit2][indices[0]],
            candidate);
          removed+=this.clearCandidateFromBlock(cells,
            cells[unit1][indices[1]],
            cells[unit2][indices[1]],
            candidate);
        }
      }
      
      if(removed>0)
      {
        this.difficultyScore+=score;
        totalRemoved+=removed;
      }
    }
  }
  while (iter.increment() && !this.breakOut);
  return totalRemoved;
}


//=============================================================================
// Remove candidate from all cells of the block in whcih cell_a and
// cell_b reside, expect cell_a and cell_b. This is used with the 2x2 subgrid.
//-----------------------------------------------------------------------------
// History
// Who When     What
// --- -------- ---------------------------------------------------------------
// ATC 03/09/05 Written.
// ATC 13/09/05 Ported to JavaScript.
//-----------------------------------------------------------------------------
Sudoku.prototype.clearCandidateFromBlock = function(cells, cellA, cellB, candidate, highlightArray)
{
  var block      = Math.floor(cellA/27)*3 + Math.floor((cellA%9)/3);
  var blockCells = this.cells.BLOCK_INDICES[block];
  var removed=0;
  for (var index = 0; index < 9; ++index)
  {
    if (blockCells[index] != cellA && blockCells[index] != cellB)
    {
      removed+=this.removeSubgridCandidate(blockCells[index], candidate, highlightArray);
    }
  }
  return removed;
}


//=============================================================================
// History
// Who When     What
// --- -------- ---------------------------------------------------------------
// ATC 13/09/05 Written.
//-----------------------------------------------------------------------------
Sudoku.prototype.removeSubgridCandidate = function(cell, candidate, highlightArray)
{
  var row = Math.floor(cell/9);
  var col = cell%9;
  var removed=0;

  if (this.isValAtXY(col, row, candidate))
  {
    removed++;
    this.addNote(mlText.methodF3_removing,{val:candidate,cell:this.cellString(col,row)});
    if(highlightArray)
    {
      highlightArray.push(new Array('cell',col,row,'pink'));
      if(this.step) this.explainAndPause(highlightArray);
      highlightArray.pop();
    }
    this.remove(col, row, candidate);
  }
  return removed;
}


//=============================================================================
function ColFromCell()
{
  this.dummy = 1;
}
ColFromCell.prototype.func = function(cell) { return cell%9; }


//=============================================================================
function RowFromCell()
{
  this.dummy = 1;
}
RowFromCell.prototype.func = function(cell) { return Math.floor(cell/9); }


//=============================================================================
//       A   B   C
//      --- --- ---
//   1 | **| * |   |
//   2 |* *| * |   |
//     |   |   |   |
//      --- --- ---
//
// If the cells marked * are the only places which can hold N in blocks A and B,
// then N cannot appear in block C in rows 1 or 2. A similar rule is applied to
// blocks and columns.
//-----------------------------------------------------------------------------
// History
// Who When     What
// --- -------- ---------------------------------------------------------------
// ATC 03/09/05 Written.
//-----------------------------------------------------------------------------
Sudoku.prototype.solveBlocksWithSharedUnits = function(score)
{
  this.cells  = new CellArrays();
  var blocks  = new BlockArrays();
  var rowFunc = new RowFromCell();
  var colFunc = new ColFromCell();
  var removed = 0;

  for (var candidate = 1; candidate <= 9 ; ++candidate)
  {
    for (var index = 0; index < 9 ; ++index)
    {
      removed+=this.solveBlocksWithSharedUnitsImpl(blocks.BLOCK_ROW_INDICES[index],
        candidate, rowFunc);
    }
    for (var index = 0; index < 9 ; ++index)
    {
      removed+=this.solveBlocksWithSharedUnitsImpl(blocks.BLOCK_COLUMN_INDICES[index],
        candidate, colFunc);
    }
  }
  if(removed>0) this.difficultyScore+=score;
  return removed;
}


//=============================================================================
// History
// Who When     What
// --- -------- ---------------------------------------------------------------
// ATC 03/09/05 Written.
//-----------------------------------------------------------------------------
Sudoku.prototype.solveBlocksWithSharedUnitsImpl = function(blocks, candidate, calc)
{
  // Find the units (rows or columns) in the first block which have the value as a candidate in
  // some cell.
  var units1 = new Array();
  var removed = 0;
  
  if (this.getUnitIndicesInBlock(this.cells.BLOCK_INDICES[blocks[0]], candidate, calc, units1) == 2)
  {
    // Find the units in the second block which have the value as a candidate in
    // some cell.
    var units2 = new Array();
    if (this.getUnitIndicesInBlock(this.cells.BLOCK_INDICES[blocks[1]], candidate, calc, units2) == 2)
    {
      // Are the two rows the same in the two blocks?
      if (units1[0] == units2[0] && units1[1] == units2[1])
      {
        for (var index = 0; index < 9; ++index)
        {
          var cell = this.cells.BLOCK_INDICES[blocks[2]][index];
          var unit = calc.func(cell);
          if (unit == units1[0] || unit == units1[1])
          {
            removed+=this.removeSubgridCandidate(cell, candidate);
          }
        }
      }
    }
  }
  return removed;
}