/* 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 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: jstr_2.js utilities_ml_2.js sudoku_ml_2.js chainfinder2.js */ mlText={ language_precursor:"", xName:["1","2","3","4","5","6","7","8","9"], yName:["A","B","C","D","E","F","G","H","I"], setCell:"Set cell %cell% to %val%.. removing %val% from related row, column & block (%togo% to go!)", startingSolveMethod:"Starting Solve Method %methodCode%", endingSolveMethod:"Ending Solve Method %methodCode%", notes:"Notes:", resetWorkingGrid:"Reset the working grid", sureClearStartGrid:"Are you sure you want to clear the START grid?", runningStartGrid:"Running Start Grid", wantToSetCell:"Want to set cell %cell% to value %val% - but it is already!", checkValid:"Checking the grid below to see if it is valid..", invalidSolution:"Invalid Sudoku solution - did not solve", validSolution:"A valid solution!", difficultyScore:"Difficulty score: %difficultyScore%", numberOfGuesses:"Number of guesses required: %guesses%", invalidSolutionCantDelete:"Invalid Sudoku or Could Not Solve - cannot delete %val% at %cell%", removing1:"Removing %val% from %cell% just leaves %cell% as %matrixValue%", foundMulticountSet:"Found a multicount set [%newSet%] and can eliminate stragglers:", setToNewSet:"Set cell %cell% to %newSet%", endLogic:"Reached end of logic.. using guessing technique called Ariadne's thread", guessing:"Guessing %val% at %cell%..", guessingSucceeded:"Guessing %val% at %cell% succeeded", guessingFailed:"Guessing %val% at %cell% failed", endOfAriadne:"End of the Ariadne's thread.. backing out.", stepSolveCancelled:"Solve by steps cancelled.", checkingGridValid:"Checking the grid to see if it is valid..", couldNotSolveBySteps:"Could not solve by steps - need to guess a cell!", timeElapsed:"Time elapsed: %secs% seconds", solvedByLogicOnly:"Solved it by logic only - a unique solution!", guessedBut1Solution:"Solved it but had to guess (but checked there is only one solution)", guessedMaybeMoreThan1Solution:"Solved it but had to guess (and there might be more than one solution)", solvedButMoreThan1Solution:"Solved it but there is more than one solution (see notes)", solvedButNSolutions:"Solved it but there are %solutions% possible solutions (see notes)", didntSolve:"Didn't solve it!", noSolution:"Since the 'Allow guess-and-check' box was ticked,\nthe solver has checked every possible outcome,\nso there is no solution", noSolveOptions:"Either:\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.", submittingGrid:"Submitting solved grid to the sudokusolver database..", column:"column %col%", columns:"columns", row:"row %row%", rows:"rows", block:"block at %block%", methodA_column:"Grid column %col% only contains one %val% at row %row%..", methodA_row:"Grid row %row% only contains one %val% at column %col%..", methodA_block:"Block at %block% only contains one %val% at cell %cell%..", methodB_row_block:"The value %val% in row %row% must lie in block at %block%..", methodB_col_block:"The value %val% in column %col% must lie in block at %block%..", methodB_block_col:"The value %val% in block at %block% must lie in column %col%..", methodB_block_row:"The value %val% in block at %block% must lie in row %row%..", methodD_name:"D: Finding number chains", methodD_info:"Checking for chains of size %size%", methodD_check_row:"Checking for chains in grid rows..", methodD_check_col:"Checking for chains in grid columns..", methodD_check_block:"Checking for chains in grid blocks..", methodD_row:"row %row%", methodD_column:"column %col%", methodD_block:"block at %block%", methodD2_found:"Found a chain in %name%: { %items% } MUST be in cells %chain%", methodD2_removing:".. removing %item% from %cell% using chain rule (method D)", methodD2_nothing_removed:".. but not able to eliminate any numbers based on this finding", methodF3_name2:"F(2): Finding X-Wing patterns...", methodF3_name3:"F(3): Finding Swordfish patterns...", methodF3_name4:"F(4): Finding Jellyfish(?) patterns...", methodF3_name5:"F(5): Finding Squirmbag (who names these things?) patterns...", methodF3_nameN:"F(%n%): Finding Uber-Squirmbag (who names these things?) patterns...", methodF3_found:"Found one for value %val% in %row_name% %row_chain% at %col_name% %col_chain%", methodF3_removing:".. removing %val% from %cell% using pattern rule (method F).", cookie_not_set:"Could not set the cookie.\nIf you want to use cookies,\nplease check your security settings.", cookie_unavailable:"Unable to get cookie data or no cookie set.", cookie_invalid:"Unable to set using cookie data", string_format_message:"Please enter the Sudoku string by rows - '_' for a blank, '+' for a new row", string_error_in_format:"Error.. Please try again. Use '_' for a blank, '+' for a new row", copy_string_to_clipboard:"Copy this to the clipboard and paste it where you want it, then hit OK", noGridsToday:"No grids today, or the database is off line.", loadThisOne:"Load this one", uniqueSolution:"Unique Solution: %isUnique%", hitCount:"Hit count: %hits%", yes:"Yes", noGreaterThanOne:"No (>1)", noNone:"No (None)" }; 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)
}