javascript实现数独解法
生生把写过的java版改成javascript版，第一次写，很不专业，见谅。唉，我是有多闲。
varSudoku={
init:function(str){
this.blank=[];
this.fixed=[];
this.cell=[];
this.trials=[];
for(i=0;i<81;i++){
varchr=str.charCodeAt(i);
if(chr==48){
this.cell[i]=511;
this.blank.push(i);
}else{
this.cell[i]=1<<chr-49;
this.fixed.push(i);
}
}
},
showBoard:function(){
varboard="";
for(vari=0;i<81;i++){
if(i%9==0){
board=board.concat("\n");
}
board=board.concat("[");
for(varj=0;j<9;j++){
if((this.cell[i]>>j&1)==1){
board=board.concat(String.fromCharCode(j+49));
}
}
board=board.concat("]");
}
returnboard;
},
check:function(){
varcheckpoint=[0,12,24,28,40,52,56,68,80];
for(variincheckpoint){
varr,b,c;
r=b=c=this.cell[checkpoint[i]];
for(j=0;j<8;j++){
c^=this.cell[this.getX(checkpoint[i])[j]];
b^=this.cell[this.getX(checkpoint[i])[8+j]];
r^=this.cell[this.getX(checkpoint[i])[16+j]];
}
if((r&b&c)!=0x1FF){
returnfalse;
}
}
returntrue;
},
bitCount:function(i){
varn=0;
for(varj=0;j<9;j++){
if((i>>j&1)==1)
n++;
}
returnn;
},
numberOfTrailingZeros:function(i){
varn=0;
for(varj=0;j<9;j++){
if((i>>j&1)==0)
n++;
else{
break;
}
}
returnn;
},
updateCandidates:function(){
for(variinthis.fixed){
varopt=0x1FF^this.cell[this.fixed[i]];
for(varj=0;j<24;j++){
this.cell[this.getX(this.fixed[i])[j]]&=opt;
//!notice
if(this.cell[this.getX(this.fixed[i])[j]]==0){
//console.log("Error-0candidate:"+x[this.fixed[i]][j]);
returnfalse;
}
}
}
returntrue;
},
seekUniqueCandidate:function(){
for(varbidxinthis.blank){
varrow=0,col=0,box=0;
for(i=0;i<8;i++){
row|=this.cell[this.getX(this.blank[bidx])[i]];
box|=this.cell[this.getX(this.blank[bidx])[8+i]];
col|=this.cell[this.getX(this.blank[bidx])[16+i]];
}
if(this.bitCount(this.cell[this.blank[bidx]]&~row)==1){
this.cell[this.blank[bidx]]&=~row;
continue;
}
if(this.bitCount(this.cell[this.blank[bidx]]&~col)==1){
this.cell[this.blank[bidx]]&=~col;
continue;
}
if(this.bitCount(this.cell[this.blank[bidx]]&~box)==1){
this.cell[this.blank[bidx]]&=~box;
}
}
},
seekFilledable:function(){
this.fixed=[];
var_del=[];
for(variinthis.blank){
if(this.bitCount(this.cell[this.blank[i]])==1){
this.fixed.push(this.blank[i]);
//console.log("fixed:"+this.blank[i]+"=>"+this.cell[this.blank[i]]);
//this.blank.splice(i,1);//todeleteitintheloopwouldcausebug
_del.push(i);
}
}
while(_del.length>0){
this.blank.splice(_del.pop(),1);
}
},
seekMutexCell:function(){
vartwo=[];
for(varninthis.blank){
if(this.bitCount(this.cell[this.blank[n]])==2){
two.push(this.blank[n]);
}
}
for(vari=0;i<two.length;i++){
for(varj=i+1;j<two.length;j++){
if(this.cell[two[i]]==this.cell[two[j]]){
varopt=~this.cell[two[i]];
if(parseInt(two[i]/9)==parseInt(two[j]/9)){
for(n=0;n<8;n++){
this.cell[this.getX(two[i])[n]]&=opt;
}
}
if((two[i]-two[j])%9==0){
for(n=8;n<16;n++){
this.cell[this.getX(two[i])[n]]&=opt;
}
}
if((parseInt(two[i]/27)*3+parseInt(two[i]%9/3))==(parseInt(two[j]/27)*3+parseInt(two[j]%9/3))){
for(n=16;n<24;n++){
this.cell[this.getX(two[i])[n]]&=opt;
}
}
this.cell[two[j]]=~opt;
}
}
}
},
basicSolve:function(){
do{
if(!this.updateCandidates(this.fixed)){
this.backForward();
}
this.seekUniqueCandidate();
this.seekMutexCell();
this.seekFilledable();
}while(this.fixed.length!=0);
returnthis.blank.length==0;
},
setTrialCell:function(){
for(variinthis.blank){
if(this.bitCount(this.cell[this.blank[i]])==2){
vartrialValue=1<<this.numberOfTrailingZeros(this.cell[this.blank[i]]);
varwaitingValue=this.cell[this.blank[i]]^trialValue;
//console.log("try:["+this.blank[i]+"]->"+(this.numberOfTrailingZeros(trialValue)+1)+"#"+(this.numberOfTrailingZeros(waitingValue)+1));
this.cell[this.blank[i]]=trialValue;
this.trials.push(this.createTrialPoint(this.blank[i],waitingValue,this.cell));
returntrue;
}
}
returnfalse;
},
backForward:function(){
if(this.trials.length==0){
console.log("Maybenosolution!");
return;
}
varback=this.trials.pop();
this.reset(back.data);
this.cell[back.idx]=back.val;
this.fixed.push(back.idx);
//console.log("back:["+back.idx+"]->"+(this.numberOfTrailingZeros(back.val)+1));
},
reset:function(data){
this.blank=[];
this.fixed=[];
this.cell=data.concat();
for(vari=0;i<81;i++){
if(this.bitCount(this.cell[i])!=1){
this.blank.push(i);
}else{
this.fixed.push(i);
}
}
},
trialSolve:function(){
while(this.blank.length!=0){
if(this.setTrialCell()){
this.basicSolve();
}else{
if(this.trials.length==0){
//console.log("Can'tgobackforward!Maybenosolution!");
break;
}else{
this.backForward();
this.basicSolve();
}
}
}
},
play:function(){
console.log(this.showBoard());
varstart=newDate().getMilliseconds();
if(!this.basicSolve()){
this.trialSolve();
}
varend=newDate().getMilliseconds();
console.log(this.showBoard());
if(this.check()){
console.log("["+(end-start)+"msOK!]");
}else{
console.log("["+(end-start)+"ms,cannotsolveit?");
}
//returnthis.showBoard();
},
getX:function(idx){
varneighbors=newArray(24);
varbox=newArray(0,1,2,9,10,11,18,19,20);
varr=parseInt(idx/9);
varc=idx%9;
varxs=parseInt(idx/27)*27+parseInt(idx%9/3)*3;
vari=0;
for(varn=0;n<9;n++){
if(n==c)continue;
neighbors[i++]=r*9+n;
}
for(varn=0;n<9;n++){
if(n==r)continue;
neighbors[i++]=c+n*9;
}
for(varn=0;n<9;n++){
vart=xs+box[n];
if(t==idx)continue;
neighbors[i++]=t;
}
returnneighbors;
},
createTrialPoint:function(idx,val,board){
vartp={};
tp.idx=idx;
tp.val=val;
tp.data=board.concat();
returntp;
}
};
//Sudoku.init("000000500000008300600100000080093000000000020700000000058000000000200017090000060");
//Sudoku.init("530070000600195000098000060800060003400803001700020006060000280000419005000080079");
Sudoku.init("800000000003600000070090200050007000000045700000100030001000068008500010090000400");
Sudoku.play();
以上就是关于使用javascript实现数独解法的全部代码了，希望大家能够喜欢。