/* SuDoku Solver by Logic v1.4 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 This is all the Javascript files [apart from jstr_2.js] compacted into one to improve web caching efficiency, with comments removed. If you want to see how the Javascript is working please download the individual files. Files in this volume as follows: utilities_ml_2.js sudoku_ml_2.js chainfinder2.js */ Date.prototype.addDays=function(d) { with(this) setTime(getTime()+d*86400000);} String.prototype.trim=function() { return this.replace(/(^\s*)|(\s*$)/g, "");} String.prototype.anyMatch=function(compareString) { var i,c; for(i=0;i=0) return true;} return false;} String.prototype.firstMatch=function(compareString) { var i,c; for(i=0;i=0) return c;} return false;} Object.prototype.complexCopyOf=function(copyTo) { var el; for(el in this) { copyTo[el]=this[el].copyOf();} return copyTo;} Object.prototype.copyOf=function() { if(this.constructor==Function) return this.constructor; if(this.constructor==Boolean || this.constructor==Number || this.constructor==String) return this.valueOf(); if(this.constructor==Array) return this.complexCopyOf(new Array()); if(this.constructor==Date) return new Date(this.getTime()); return this.complexCopyOf(new this.constructor);} Array.prototype.showHTML=function() { var i,a0; a0=""; for(i=0;i";} 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("
")!=-1) this.lastNoteButOne=""; this.lastNote=str; this.bufferNotes+=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("
"+this.statusNoteText("
")+"
");}
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+"
"; 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("\"\""); this.workingGridDiv.innerHTML=this.showHTML("\"\""); 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(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=""; var x,y; a0+=""; a0+=""; for(x=0;x<9;x++)
{ a0+="";}
a0+=""; for(y=0;y<9;y++)
{ a0+=""; a0+=""; 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+=""+eval(evalStr)+"";}
a0+="";}
a0+="
"+this.xName[x]+"
"+this.yName[y]+"
"; return a0;}
Sudoku.prototype.runStartGrid=function()
{ var x,y; this.breakOut=false; this.addNote("=============================="); this.addNote(""+mlText.runningStartGrid+""); 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=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=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=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=0)
{ vc++;}
}
if(vc==vals.length)
{ ct++; this.lastFoundX=x; this.lastFoundY=y; this.found.push(new Array(x,y));}
}
}
return ct;}
Sudoku.prototype.findUnique=function(foundCountOf,c)
{ var curEl,compareEl,matches,i,j,matchedEl,elimOne,newSet; elimOne=false; while(foundCountOf.length>=c)
{ curEl = foundCountOf.shift(); matches=null; matches=new Array(); for(i=0;i1)
{ found=true; break;}
}
if(found==true) break;}
if(found==false) return false; this.addNote("
"+mlText.endLogic+"
"); this.statusNote(); tempSolvedCount=this.solvedCount; savedMatrix=this.getMatrixString(); solvedAtAll=false; for(n=0;n"+mlText.guessing+"
",{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)
{ this.addNote(e); solved=false;}
solvedAtAll|=solved; if(solved)
{ this.addNote("
"+mlText.guessingSucceeded+"
",{val:val,cell:this.cellString(x,y)});}
else
{ this.addNote("
"+mlText.guessingFailed+"
",{val:val,cell:this.cellString(x,y)});}
if(solved && this.returnFirstAnswer) return true; if(solved && this.solutions>=2 && this.stopAfterTwoSolutions) return true; this.solvedCount=tempSolvedCount; this.setMatrixString(savedMatrix);}
this.addNote("
"+mlText.endOfAriadne+"
"); 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(); 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(); 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.prototype.solveMethodA=function()
{ 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()
{ 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(x=0;x<9;x++)
{ for(n=1;n<=9;n++)
{ cc=this.columnCount(x,n); if(cc<=3 && cc>1)
{ b0=1;b1=1;b2=1; for(i=0;i=6) b2=2; else b1=2;}
if(b0*b1*b2==2)
{ bx=3*parseInt(x/3); by=b1*3+b2*6-9; 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;i1)
{ b0=1;b1=1;b2=1; for(i=0;i=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;i1)
{ allSameRow=true; allSameCol=true; for(i=1;icc)
{ 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;i2+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;i2+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)
{ 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)
{ 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)
{ 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)
{ 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");}
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);}
function VectorIterator(size, range)
{ this.range = range; this.indices = new Array(); for (var i = 0; i < size; ++i)
{ this.indices[i] = i;}
}
VectorIterator.prototype.increment = function()
{ var size = this.indices.length; while (true)
{ 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;}
if (this.indices[0] >= this.range + 1 - size)
return false;}
}
function Subset()
{ this.reference = 0; this.items = new Array();}
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)
{ var already_present = false; for (var k = 0; k < items.length; ++k)
{ if (items[k] == subset.items[j])
{ already_present = true; break;}
}
if (!already_present)
items.push(subset.items[j]);}
}
items.sort(); return items.length;}
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;}
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'));}
}
this.addNote(""); this.endMethodNote("D");}
Sudoku.prototype.solveSubsetsByCandidate = function(cells, subsetSize, name, score, baseHighlightEl)
{ var highlightArray; 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);}
}
if (subsets.length < subsetSize)
return 0; var removedTotal = 0; var iter = new VectorIterator(subsetSize, subsets.length); do
{ var items = new Array(); var references = new Array(); if (createUnionOfSubsets(iter, subsets, items, references) == subsetSize)
{ 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}); var removed = 0; for (var index = 0; index < 9; ++index)
{ var reset_allowed = true; for (var i = 0; i < references.length; ++i)
{ if (references[i] == index)
{ reset_allowed = false; break;}
}
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;}
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);}
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;}
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;}
function arrayContains(container, value)
{ var result = false; for (var i = 0; i < container.length; ++i)
{ if (container[i] == value)
{ result = true; break;}
}
return result
}
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");}
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; var size = this.getIndicesInUnit(cells[unit], candidate, subset.items); if (size > 1 && size <= subsetSize)
{ subset.reference = unit; subsets.push(subset);}
}
if (subsets.length < subsetSize)
return 0; var iter = new VectorIterator(subsetSize, subsets.length); do
{ var indices = new Array(); var units = new Array(); 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}); 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);}
}
}
if (subsetSize == 2)
{ var unit1 = units[0]; var unit2 = units[1]; 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;}
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;}
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);}
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;}
Sudoku.prototype.solveBlocksWithSharedUnitsImpl = function(blocks, candidate, calc)
{ var units1 = new Array(); var removed = 0; if (this.getUnitIndicesInBlock(this.cells.BLOCK_INDICES[blocks[0]], candidate, calc, units1) == 2)
{ var units2 = new Array(); if (this.getUnitIndicesInBlock(this.cells.BLOCK_INDICES[blocks[1]], candidate, calc, units2) == 2)
{ 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;}
function indexLink(index,cvs)
{ this.index=index; this.cvs=cvs;}
indexLink.prototype.showHTML=function()
{ return "["+this.index+" - "+this.cvs+" ]"
}
function ChainFinder(chainArray)
{ this.chainArray=chainArray; this.foundChainSet=new Array(); this.foundChainSetNumbers=new Array(); this.inChain=new Array();}
ChainFinder.prototype.findChains=function()
{ var i,linkSet; this.foundChainSet=null; this.foundChainSet=new Array(); linkSet=new Array(); for(i=0;i"
for(j=0;jGetting chain length "+remainingLinks.length); this.debug(remainingLinks.showHTML()); if(link==null || linkedSet==null || unLinkedSet==null)
{ while(remainingLinks.length>0)
{ link=remainingLinks.shift(); this.getChain(remainingLinks,link,new Array(),new Array());}
}
else
{ this.debug(link.showHTML()); this.debug(linkedSet.showHTML()); this.debug(unLinkedSet.showHTML());}
if(link.cvs.length==1) return; while(remainingLinks.length>0)
{ testLink=remainingLinks.shift(); if(this.areLinked(link, testLink))
{ this.debug(link.showHTML()+" and "+testLink.showHTML()+" are linked."); linkedSet.push(link); link=testLink; if(this.isChain(linkedSet,link))
{ this.debug("Found set "+linkedSet.showHTML()); linkedSet.push(link); this.saveChain(linkedSet); while(remainingLinks.length>0)
{ unLinkedSet.push(remainingLinks.shift());}
break;}
else
{ this.debug("Not a chain though - recursing.."); for(i=0;i0) this.getChain(unLinkedSet)
}