/*
SuDoku Solver by Logic v1.2
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
*/

function Sudoku(startGridDiv,workingGridDiv,notesName)
{
  this.xName=new Array("1","2","3","4","5","6","7","8","9");
  this.yName=new Array("A","B","C","D","E","F","G","H","I");
  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.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.latestSolution="";
  this.doAriadne=true;
  this.returnFirstAnswer=true;
  this.stopAfterTwoSolutions=true;

  this.lsEl=null;

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

  this.bufferNotes="";
  this.lastNote="";
  this.lastNoteButOne="";
  this.notesDoc.body.innerHTML="Notes:<br>";
}

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




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

Sudoku.prototype.addNote=function(str,worthPause,x,y)
{
  this.lastNoteButOne=this.lastNote;
  this.lastNote=str;
  this.bufferNotes+=str+"<br>";
  /*
  if(x && y)
  {
    if(this.lsEl!=null) this.lsEl.style.backgroundColor='';
    this.lsEl=document.getElementById("sgw_"+x+"_"+this.lastFoundY);
    this.lsEl.style.backgroundColor='#FFD700';
  }
  */
  //if(worthPause==true) alert(str);
}

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("Starting Solve Method "+methodCode);
  this.statusNote();
}

Sudoku.prototype.endMethodNote=function(methodCode)
{
  if(this.step==true) this.refreshWorkingGrid();
  this.addNote("Ending Solve Method "+methodCode);
  this.addNote("==============================");
}



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

  this.refreshWorkingGrid();
  this.notesDoc.body.innerHTML="Notes:<br>";
  this.addNote("Reset the working grid");
  this.solvedCount=0;
}




Sudoku.prototype.clearStartGrid=function()
{
  var csg=confirm('Are you sure you want to clear the START grid?');
  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.initialiseDivs=function()
{
  this.startGridDiv.innerHTML=this.showHTML("\"<input type='text' id='sgd_\"+x+\"_\"+y+\"' value='' size='1' maxlength='1' style='font-family:arial narrow; text-align:center;'>\"");
  this.workingGridDiv.innerHTML=this.showHTML("\"<input type='text' id='sgw_\"+x+\"_\"+y+\"' value='' size='9' maxlength='9' style='font-family:arial narrow; text-align:center;'></>\"")
  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='';
    }
  }
}




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

  a0="<table cellpadding=1 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)?"#8470FF ":"white ";
      styleStr+=(x%3==2)?"#8470FF ":"white ";
      styleStr+=(y%3==2)?"#8470FF ":"white ";
      styleStr+=(x%3==0)?"#8470FF":"white";
      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>Running Start Grid</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.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.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("Want to set cell "+this.cellString(x,y)+" to "+val+" - but it is already!");
    return;
  }
  
  this.solvedCount++;

  this.addNote("Set cell "+this.cellString(x,y)+" to "+val+": Removing "+val+" from related row, column & block ("+(81-this.solvedCount)+" to go!)");

  if(this.solvedCount==81)
  {
    this.addNote("Checking the grid below to see if it is valid..");
    this.statusNote();
    if(this.checkSolution()!=true)
    {
      throw "Invalid soduku solution - did not solve";
    }
    this.solutions++;
    this.latestSolution=this.getMatrixString();
    this.addNote("A valid solution!");
    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.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 "Invalid Sudoku or Could Not Solve - cannot delete "+val+" at "+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("Removing "+val+" from "+this.cellString(x,y)+" just leaves "+this.cellString(x,y)+" as "+this.matrix[y][x]);
      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("Found a multicount set ["+newSet+"] and can eliminate stragglers:");
        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("Setting "+this.cellString(curEl[1][j][0],curEl[1][j][1])+" to "+newSet);
          this.matrix[curEl[1][j][1]][curEl[1][j][0]]=newSet;
          this.hasChangedFlag=true;
        }
      }
    }
  }
  return elimOne;
}


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

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.solveMethodD();
    if(this.hasChangedFlag==true || this.breakOut==true) continue;

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

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


Sudoku.prototype.ariadnesThread=function()
{
  var x,y,n,val,tempSolvedCount,savedMatrix;
  
  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;

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

  for(n=0;n<this.matrix[y][x].length;n++)
  {
    val=this.matrix[y][x].charAt(n);
    this.addNote("<br><b>Guessing "+val+" at "+this.cellString(x,y)+"</b><br>");
    this.statusNote();
    try
    {
      this.set(x,y,val,true);
      solved=this.ariadnesThread();
      if(solved && this.returnFirstAnswer) return true;
      if(solved && this.solutions>=2 && this.stopAfterTwoSolutions) return true;
    }
    catch (e)
    {
      this.addNote(e);
      //invalid solution
    }

    //otherwise continue
    //return to saved status
    this.addNote("<br><b>Guessing "+val+" at "+this.cellString(x,y)+" failed - try next</b><br>");
    this.solvedCount=tempSolvedCount;

    this.setMatrixString(savedMatrix);
  }
  this.addNote("<br><b>No solutions for this thread.. backing out.</b></br>");
}


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


Sudoku.prototype.solveBySteps=function()
{
  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("Solve by steps cancelled.");
  if(this.solvedCount==81)
  {
    this.addNote("Checking the grid to see if it is valid..");
    this.statusNote();
    if(this.checkSolution()!=true)
    {
      this.addNote("Invalid soduku solution - did not solve");
    }
    else
    {
      this.addNote("A valid solution!");
      alert("A valid solution!");
    }
  }
  else if(this.breakOut==false)
  {
    this.addNote("Could not solve by steps - need to guess a cell!");
    alert("Could not solve by steps - need to guess a cell!");
  }
  this.echoNotes();
  this.refreshWorkingGrid();
}

Sudoku.prototype.suggestAMove=function()
{
  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 a0=getSudokuString("x");
  if(this.lastSubmittedGrid!=a0 && mostPopularGrid!=a0)
  {
    submitGrid();
    this.lastSubmittedGrid=a0;
  }

  saveCurrentGrid(); //if possible

  this.solutions=0;
  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("Time elapsed: "+(elapsedTime/1000)+" seconds");
    this.echoNotes();

    if(this.solutions>0)
    {
      this.setMatrixString(this.latestSolution);
      this.refreshWorkingGrid();
      if(this.solutions==1 && this.returnFirstAnswer)
      {
        alert("Solved it!")
      }
      else if(this.solutions==1 && !this.returnFirstAnswer)
      {
        alert("Solved it - a unique solution!")
      }
      else if(this.solutions==2 && this.stopAfterTwoSolutions)
      {
        alert("Solved it - but more than one solution!");
      }
      else
      {
        alert("Solved it - but "+this.solutions+" solutions!");
      }
    }
    else
    {
      if(this.doAriadne)
      {
        alert("Didn't solve it!\nSince the 'Allow guess-and-check' box was ticked,\nthe solver has checked every possible outcome,\nso there is no solution");
      }
      else
      {
        alert("Didn't solve it!\nEither:\n(1) Tick the 'allow guess-and-check' box, or\n(2) Using the current solution grid, try working out a number by logic,\nenter it in the start grid, and see if that works.");
      }
    }
  }
  catch (e)
  {
    this.echoNotes();
    this.refreshWorkingGrid();
    alert(e);
  }
}



/////////////////////////////////////////////////////////////////////////////////////////////////
//
//
//  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("Grid column "+this.xName[x]+" only contains one "+n+" at row "+this.yName[this.lastFoundY]+"..",true,x,this.lastFoundY);
          if(this.step) this.explainAndPause(new Array(new Array('col',x,'#98FB98'),new Array('cell',x,this.lastFoundY,'#FFD700')));
          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("Grid row "+this.yName[y]+" only contains one "+n+" at column "+this.xName[this.lastFoundX]+"..",true);
          if(this.step) this.explainAndPause(new Array(new Array('row',y,'#98FB98'),new Array('cell',this.lastFoundX,y,'#FFD700')));
          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("Block at "+this.cellString(bx*3,by*3)+" only contains one "+n+" at position "+this.cellString(this.lastFoundX,this.lastFoundY)+"..",true);
            if(this.step) this.explainAndPause(new Array(new Array('block',bx*3,by*3,'#98FB98'),new Array('cell',this.lastFoundX,this.lastFoundY,'#FFD700')));
            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("The value "+n+" in block "+this.cellString(bx,by)+" must lie in column "+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.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("The value "+n+" in block "+this.cellString(bx,by)+" must lie in 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.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("The value "+n+" in row "+this.yName[this.found[0][1]]+" must lie in 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.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("The value "+n+" in column "+this.xName[this.found[0][0]]+" must lie in 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.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.prototype.solveMethodD=function()
{
/*
Look at a row in the solution grid to see if there are any cells that form number chains -
as simple as [18]-[18] or as complex as [123]-[234]-[341]-[412]. If so, these cell must be the cells
that contain those numbers, so eliminate the numbers in the chain from all the other cells in the line.
Repeat for columns and blocks
*/
  var x,y,bx,by,n,val,foundOne;
  var chainFinder;
  var numbersEliminatedCount;
  var highlightArray;

  this.startMethodNote("D");

  foundOne=false;
  for(x=0;x<9;x++)
  {
    tempArr=new Array();
    for(y=0;y<9;y++)
    {
      tempArr.push(this.matrix[y][x]);
    }
    chainFinder = new ChainFinder(tempArr);
    chainFinder.findChains();
    if(chainFinder.foundChainSet.length==0) continue;
    this.addNote("Found a chain in column "+this.xName[x]+": "+chainFinder.foundChainSet.showHTML());
    highlightArray=new Array(new Array('col',x,'#8470FF'));
    for(i=0;i<chainFinder.foundChainSet.length;i++)
    {
      for(j=0;j<chainFinder.foundChainSet[i].length;j++)
      {
        highlightArray.push(new Array('cell',x,chainFinder.foundChainSet[i][j].index,'#98FB98'));
      }
    }
    numbersEliminatedCount=0;
    // now look for cells that are NOT in the chain..
    for(y=0;y<9;y++)
    {
      if(chainFinder.inChain[y]!=null) continue;
      // but that contain a number that IS in the chain
      for(ix=0;ix<chainFinder.foundChainSetNumbers.length;ix++)
      {
        // we can eliminate that number from that cell, because it HAS to be in one of the chain cells
        while(val=this.matrix[y][x].firstMatch(chainFinder.foundChainSetNumbers[ix]))
        {
          this.addNote(".. Removing number "+val+" from "+this.cellString(x,y)+" using chain rule");
          highlightArray.push(new Array('cell',x,y,'pink'));
          if(this.step) this.explainAndPause(highlightArray);
          highlightArray.pop();

          this.remove(x,y,val);
          
          numbersEliminatedCount++;
        }
      }
    }
    if(numbersEliminatedCount==0) this.addNote(".. But not able to eliminate any numbers based on this finding");

    if(this.breakOut==true) return this.endMethodNote("D");
  }

  for(y=0;y<9;y++)
  {
    tempArr=new Array();
    for(x=0;x<9;x++)
    {
      tempArr.push(this.matrix[y][x]);
    }
    chainFinder = new ChainFinder(tempArr);
    chainFinder.findChains();
    if(chainFinder.foundChainSet.length==0) continue;
    this.addNote("Found a chain in row "+this.yName[y]+": "+chainFinder.foundChainSet.showHTML());
    highlightArray=new Array(new Array('row',y,'#8470FF'));
    for(i=0;i<chainFinder.foundChainSet.length;i++)
    {
      for(j=0;j<chainFinder.foundChainSet[i].length;j++)
      {
        highlightArray.push(new Array('cell',chainFinder.foundChainSet[i][j].index,y,'#98FB98'));
      }
    }
    numbersEliminatedCount=0;
    for(x=0;x<9;x++)
    {
      if(chainFinder.inChain[x]!=null) continue;
      for(ix=0;ix<chainFinder.foundChainSetNumbers.length;ix++)
      {
        while(val=this.matrix[y][x].firstMatch(chainFinder.foundChainSetNumbers[ix]))
        {
          this.addNote(".. Removing number "+val+" from "+this.cellString(x,y)+" using chain rule");
          highlightArray.push(new Array('cell',x,y,'pink'));
          if(this.step) this.explainAndPause(highlightArray);
          highlightArray.pop();

          this.remove(x,y,val);
          numbersEliminatedCount++;
        }
      }
    }
    if(numbersEliminatedCount==0) this.addNote(".. But not able to eliminate any numbers based on this finding");
    if(this.breakOut==true) return this.endMethodNote("D");
  }

  for(mx=0;mx<9;mx+=3)
  {
    for(my=0;my<9;my+=3)
    {
      tempArr=new Array();
      for(bx=0;bx<3;bx++)
      {
        for(by=0;by<3;by++)
        {
          tempArr.push(this.matrix[my+by][mx+bx]);
        }
      }
      chainFinder = new ChainFinder(tempArr);
      chainFinder.findChains();
      if(chainFinder.foundChainSet.length==0) continue;
      this.addNote("Found a chain in block at "+this.cellString(mx,my)+": "+chainFinder.foundChainSet.showHTML());
      highlightArray=new Array(new Array('block',mx,my,'#8470FF'));
      for(i=0;i<chainFinder.foundChainSet.length;i++)
      {
        for(j=0;j<chainFinder.foundChainSet[i].length;j++)
        {
          var osi=chainFinder.foundChainSet[i][j].index;
          var osy=osi%3;
          var osx=(osi-osy)/3;
          highlightArray.push(new Array('cell',mx+osx,my+osy,'#98FB98'));
        }
      }
      numbersEliminatedCount=0;
      for(bx=0;bx<3;bx++)
      {
        for(by=0;by<3;by++)
        {
          if(chainFinder.inChain[bx*3+by]!=null) continue;
          for(ix=0;ix<chainFinder.foundChainSetNumbers.length;ix++)
          {
            while(val=this.matrix[my+by][mx+bx].firstMatch(chainFinder.foundChainSetNumbers[ix]))
            {
              this.addNote(".. Removing number "+val+" from "+this.cellString(mx+bx,my+by)+" using chain rule");
              
              highlightArray.push(new Array('cell',mx+bx,my+by,'pink'));
              if(this.step) this.explainAndPause(highlightArray);
              highlightArray.pop();

              this.remove(mx+bx,my+by,val);
              numbersEliminatedCount++;
            }
          }
        }
      }
      if(numbersEliminatedCount==0) this.addNote(".. But not able to eliminate any numbers based on this finding");
      if(this.breakOut==true) return this.endMethodNote("D");
    }
  }
  this.endMethodNote("D");
}





Sudoku.prototype.solveMethodF=function()
{
/*
Look at a row to find instances where a number occurs in two cells only
If there are any other rows that satisfy the same rule with the same number,
and the cell columns match in both cases, then that number must be in one of those four cells

You can therefore eliminate any occurances of that number in the matching columns

*/
  var x,xx,xxx,y,yy,yyy,i,bx,by,n, foundOne,foundCountOf;

  this.startMethodNote("F");


  for(x=0;x<9;x++)
  {
    for(n=1;n<=9;n++)
    {
      if(this.columnCount(x,n)==2)
      {
        found1=this.found.copyOf(); //save the found set
        for(xx=x+1;xx<9;xx++) // move down the grid
        {
          if(this.columnCount(xx,n)==2) // a possible match
          {
            foundOne=true; //..now test for failure
            for(i=0;i<found1.length;i++)
            {
              if(found1[i][1]!=this.found[i][1]) // same y-position [will always be in order!]
              {
                foundOne=false;
                break;  //out of i-loop
              }
            }
            if(foundOne==true) //a match! eliminate the number
            {
              this.addNote("Found a double match for "+n+" in columns "+this.xName[x]+" and "+this.xName[xx]+" and columns "+this.yName[found1[0][1]]+" and "+this.yName[found1[1][1]]);

              for(xxx=0;xxx<9;xxx++)
              {
                if(xxx==x || xxx==xx) continue;
                for(i=0;i<found1.length;i++)
                {
                  if(this.isValAtXY(xxx,found1[i][1],n))
                  {
                    this.addNote(".. Removing number "+n+" from "+this.cellString(xxx,found1[i][1])+" using Solve Method F");
                    if(this.step) this.explainAndPause(new Array(new Array('cell',x,found1[0][1],'#8470FF'),new Array('cell',x,found1[1][1],'#8470FF'),new Array('cell',xx,found1[0][1],'#8470FF'),new Array('cell',xx,found1[1][1],'#8470FF'),new Array('cell',xxx,found1[i][1],'#98FB98')));
                    foundOne=true;
                    this.remove(xxx,found1[i][1],n);
                  }
                }
              }
            }
          }
        }
        //this.addNote("Found "+c+" counts of "+n+" in row "+y);
      }
    }
    if(this.breakOut==true) return this.endMethodNote("F");
  }


  for(y=0;y<9;y++)
  {
    for(n=1;n<=9;n++)
    {
      if(this.rowCount(y,n)==2)
      {
        found1=this.found.copyOf(); //save the found set
        for(yy=y+1;yy<9;yy++) // move down the grid
        {
          if(this.rowCount(yy,n)==2) // a possible match
          {
            foundOne=true; //..now test for failure
            for(i=0;i<found1.length;i++)
            {
              if(found1[i][0]!=this.found[i][0]) // same x-position [will always be in order!]
              {
                foundOne=false;
                break;  //out of i-loop
              }
            }
            if(foundOne==true) //a match! eliminate the number
            {
              this.addNote("Found a double match for "+n+" in rows "+this.yName[y]+" and "+this.yName[yy]+" and columns "+this.xName[found1[0][0]]+" and "+this.xName[found1[1][0]]);

              for(yyy=0;yyy<9;yyy++)
              {
                if(yyy==y || yyy==yy) continue;
                for(i=0;i<found1.length;i++)
                {
                  if(this.isValAtXY(found1[i][0],yyy,n))
                  {
                    this.addNote(".. Removing number "+n+" from "+this.cellString(found1[i][0],yyy)+" using Solve Method F");
                    if(this.step) this.explainAndPause(new Array(new Array('cell',found1[0][0],y,'#8470FF'),new Array('cell',found1[1][0],y,'#8470FF'),new Array('cell',found1[0][0],yy,'#8470FF'),new Array('cell',found1[1][0],yy,'#8470FF'),new Array('cell',found1[i][0],yyy,'#98FB98')));
                    this.remove(found1[i][0],yyy,n);
                    foundOne=true;
                  }
                }
              }
            }
          }
        }
        //this.addNote("Found "+c+" counts of "+n+" in row "+y);
      }
    }
    if(this.breakOut==true) return this.endMethodNote("F");
  }

/*
  Rule F must surely also apply to blocks???...
  
  for(blockIx=0;blockIx<9;blockIx++)
  {
    bx=(blockIx % 3);
    by=(blockIx-bx)/3;
    for(n=1;n<=9;n++)
    {
      if(this.blockCount(bx,by,n)==2)
      {
        found1=this.found.copyOf(); //save the found set
        
        //check across the row (don't need to go up because we've already covered this)
        for(bx1=bx+1;bx1<3;bx1++)
        {
          if(this.blockCount(bx1,by,n)!=2) continue; //skip this loop
          
          
          
        }
        
        //check down the column
        for(by1=by+1;by1<3;by1++)
        {

        }
        
        
        
        for(blockIx1=blockIx+1;blockIx1<9;blockIx1++) // move down the grid
        {
          bx1=(blockIx1 % 3);
          by1=(blockIx1-bx1)/3;
          if(bx1!=bx&&by1!=by) continue; //must be in the same row or column!
          
          if(this.blockCount(bx1,by1,n)==2) // a possible match
          {
              foundOne=true; //..now test for failure
              if(bx==bx1) //it's a row test
              {
                if(
              }
              for(i=0;i<found1.length;i++)
              {
                if(found1[i][0]!=this.found[i][0]) // same x-position [will always be in order!]
                {
                  foundOne=false;
                  break;  //out of i-loop
                }
              }
              if(foundOne==true) //a match! eliminate the number
              {
                this.addNote("Found a double match for "+n+" in rows "+this.yName[y]+" and "+this.yName[yy]+" and columns "+this.xName[found1[0][0]]+" and "+this.xName[found1[1][0]]);

                for(yyy=0;yyy<9;yyy++)
                {
                  if(yyy==y || yyy==yy) continue;
                  for(i=0;i<found1.length;i++)
                  {
                    if(this.isValAtXY(found1[i][0],yyy,n))
                    {
                      this.remove(found1[i][0],yyy,n);
                      this.addNote(".. Removing number "+n+" from "+this.cellString(found1[i][0],yyy)+" using Solve Method F");
                      foundOne=true;
                    }
                  }
                }
              }
            }
          }
          //this.addNote("Found "+c+" counts of "+n+" in row "+y);
        }
      }
      if(this.breakOut==true) return this.endMethodNote("F");
  }
*/
  return this.endMethodNote("F");
}