数独游戏的一段代码，忘记了用的是深度优先还是广度优先的搜索算法，使用了些概率上的算法改进，share下，怕过几年不小心删除了， g.js 貌似另外一篇博文中有，这里就不贴了。
当初这段代码颇有些缘由，古人有曰：山不在高有仙则名，水不在深有龙则灵。编程语言本无类，不要抱怨某些语言如何如何，关键的问题还是在人。这段代码比很多native code要快，不信各位可自行验证
本来不想继续写了，回想下还是做些笔记吧，以免时间长了自己都忘记了，备注下这段代码使用的技巧：
1.js代码使用CloneNode（true）克隆DOM节点（包含子节点）创建多个九宫格，并用CSS将其渲染成不同的效果；
2.面向对象的设计结构；mvc分层设计
3.推断的时候使用可能值排除法，当无法明确推断的时候，寻找可能值个数最少的节点开始（这个是重点），先压栈保存状态，然后尝试填充，继续推断或猜测，直到得到答案，或者出错回滚排除错误值后向另一个方向继续
<!-- copy all right , barenx@163.com -->
<html><head><meta http-equiv="Content-Type" content="text/html;charset=utf-8"><meta http-equiv="Description" content="there is one shoudu online demo"><meta http-equiv="Keywords" content="shoudu;javascript;css;web design;dom"><meta http-equiv="Auther" content="barenx"><title>sodu demo--PowerBy Barenx</title><script language="javascript" type="text/javascript" src="g.js"></script><style type="text/css">body{ text-align:center; margin:5px;}/*big display number block*/#tb td, #hx td{ width:47px; height:47px; font-size:17px; font-family:Verdana, Arial, Helvetica, sans-serif; vertical-align:middle; text-align:center; work-break:break-all; border:1px #FFFFFF solid;}#tb td{ border:#ffffff dotted 1px; font-weight:bold;}#hx td{ cursor:pointer; background:#99FFFF;}/*main div block*/#lp1{ width:auto; height:auto; float:left; border:1px #00CC33 solid;}#lp1 table{ margin:2px auto}#lp1 hr{ width:480px;}/*information div block*/#rp1{ display:block; width:510px; height:auto; float:left; border:none; margin:auto 5px; padding:3px;}#rp1 td { width:14px; height:14px; font-size:11px; font-family:Verdana, Arial, Helvetica, sans-serif; vertical-align:middle; text-align:center; work-break:break-all; float:none;}#rp1 table{ table-layout:fixed; border:1px #CC0033 solid; margin:2px; float:left;}/*debug div block*/#debugWin{ width:100%; height:60px; margin:3px; display:block; padding-bottom:15px; text-align:left;}#debugWin div{ width:100%; margin:0 40px 1px 1px; padding:0 20px 0 12px; border:1px solid #000099; height:50px; overflow-y:scroll; text-align:left; word-break:break-all; font-size:10px;}#debugWin input{ width:85px; height:auto; font:Verdana, Arial, Helvetica, sans-serif; font-size:1.75ex;}</style></head><body><div id=debugWin></div><div id=lp1></div><div id=rp1></div></body><script language="javascript" type="text/javascript">//Copyright(C) 2008 BAREN Productions. All rights reserved.var ihx={ //choiced number val:0, //nine pane, td block object [1-9] O:[], //td block onclick callback function click:function(id){ if(id==this.val)return; if(this.O[this.val]){ with(this.O[this.val].style){ background="#99ffff"; color="#000"; fontWeight=""; } } var y=this.O[id]; if(!y)return false; with(y.style){ background="#ffff99"; color="#a11"; fontWeight="bold"; } this.val=id; }, //initialization function ---create events' function to change css style Create:function(id){ var tbcs=_F.$('hx').rows[0].cells,o; this.O[0]=0; for(var i=0;i<tbcs[_L];i++){ o=tbcs[i]; o.v=i+1; o.onclick=function(){ihx.click(this.v)} o.onmouseenter=function(){this.style.border="#000000 dotted 1px"} o.onmouseleave=function(){this.style.border="#ffffff dotted 1px"} this.O.push(o); } //set default value this.click(1); }},matrixs={ //O td :--y rowNum[1-9] , --x cellIndex[1-9] :--matrix [1-9]*[1-9] O:[], //dump info table tr td :--matrix [1-9]*[1-9]*[1-9] DumpDev:[], //mark if true dump information Ready:true, //set one pane set:function(y,x,v,iw){ var i,o=this.O,c=o[y][x]; if(c.isFix)return true; //debug.printTitle(p.P[v],v); if(c.P[v]!=v)return false; for(i=0;i<20;i++) c.Na[i].P[v]=''; //debug.print(c.Na[_L]); for(i=1;i<=9;i++) c.P[i]=''; c.P[v]=v; c.innerHTML=v; if(iw)c.style.color='green'; this.dump(); return c.isFix=true; }, //save data to string save:function(){ var o=matrixs.O,v=[],y,x; for(y=1;y<=9;y++){ for(x=1;x<=9;x++)v.push(o[y][x].isFix?o[y][x].innerHTML:0); } return v.join(''); //debug.stop(); }, //Load data from string load:function(s,m){ s=(s||'').replace(/\D+/g,''); if(s[_L]!=81)return debug.print('error data input,9*9 panes numbers needed!\n'); m=m||s; this.Ready=false; this.reset(); var i,x,y,a; for(i=0;i<81;i++){ y=Math.floor(i/9)+1; x=i%9+1; a=s.charAt(i); if(a>0&&a<=9)this.set(y,x,a,(a!=m.charAt(i))); } this.Ready=true; this.dump(); }, //get point value getPointVal:function(y,x){return this.O[y][x].P.join('')}, // rational value check isError:function(){ var i,j,o=this.O; for(i=1;i<=9;i++){ for(j=1;j<=9;j++){ if(this.O[i][j].P.join('')[_L]<=0) return {y:i,x:j}; } } return false; }, //check wheather the table is full filled isFull:function(){ var i,j,o=this.O; for(i=1;i<=9;i++){ for(j=1;j<=9;j++){ if(!o[i][j].isFix) return false; } } return true; }, //reset user data & display reset:function(){ var y,x,o=this.O,oy,oyx; for(y=1;y<=9;y++){ oy=o[y]; for(x=1;x<=9;x++){ oyx=oy[x]; oyx.isFix=false; oyx.innerHTML=" "; oyx.style.color="#000"; oyx.P=['',1,2,3,4,5,6,7,8,9]; } } this.dump(); }, //dump funciton to show matrix status dump:function(){ if(!this.Ready)return; var d=this.DumpDev,o=this.O,oy,dv,dvy; var v,y,x,a,b; for(v=1;v<=9;v++){ dv=d[v]; for(y=1;y<=9;y++){ dvy=dv[y];oy=o[y]; for(x=1;x<=9;x++){ a=oy[x].P[v];b=dvy[x]; if(a!=b.innerHTML)b.innerHTML=a; } } } }, setNerb:function(y,x,o){ var i,j,c=o[y][x]; for(j=1;j<=9;j++) if(j!=y)c.Ny.push(o[j][x]); for(i=1;i<=9;i++) if(i!=x)c.Nx.push(o[y][i]); var bx=Math.floor((x-1)/3)*3+1; var by=Math.floor((y-1)/3)*3+1; c.Na=c.Na.concat(c.Ny,c.Nx); //if (x==1 && y==1)debug.stop(); for(j=by;j<by+3;j++){ for(i=bx;i<bx+3;i++){ if(i!=x || j!=y) c.Nb.push(o[j][i]); if(i!=x && j!=y) c.Na.push(o[j][i]); } } }, //initialization function set variants' value,fomate matrix array Create:function(id,de) { var tbrs=_F.$(id).rows,tbcs,cell; var i,j,k,o=[0]; for(i=1;i<=9;i++){ o[i]=[0]; tbcs=tbrs[i-1].cells; for(j=0;j<tbcs[_L];j++){ cell=tbcs[j]; cell.y=i; cell.x=j+1; cell.Ny=[]; cell.Nx=[]; cell.Nb=[]; cell.Na=[]; cell.P=['',1,2,3,4,5,6,7,8,9]; cell.onclick=function(){matrixs.set(this.y,this.x,ihx.val)} cell.onmouseenter=function(){this.style.border="#000000 dotted 1px";debug.printTitle(matrixs.getPointVal(this.y,this.x))} cell.onmouseleave=function(){this.style.border="#ffffff dotted 1px"} o[i].push(cell); } } for(i=1;i<=9;i++){ for(j=1;j<=9;j++) this.setNerb(i,j,o); } delete this.setNerb; this.O=o;o=0; var d=[0],dv,dvy; for(i=1;i<=9;i++){ tbrs=_F.$(de+i).rows; dv=[0]; for(j=0;j<9;j++){ tbcs=tbrs[j].cells; dvy=[0]; for(k=0;k<9;k++)dvy.push(tbcs[k]); dv.push(dvy); } d.push(dv); } //debug.stop(); this.DumpDev=d; d=0;dv=0;dvy=0; tbcs=0;tbrs=0;cell=0; debug.f.push( { n:"save", f:function(){ debug.println(matrixs.save()); } }, { n:"load", f:function(){ matrixs.load(debug.get("input your data","")); } }, { n:"reset", f:function(){ matrixs.reset(); intelligence.reset(); } }, { n:"intelligence", f:function(){ intelligence.start(); } }, { n:"check", f:function(){ var rlt=matrixs.isError(); debug.println(rlt?['point(',rlt.y,",",rlt.x,') has no choice!']:'check ok!'); } } ); }},//intelligence functions can guess the right number in the cell be filledintelligence={ org:'', buf:[], lastMin:1, timer:0, //reset program clear buf reset:function(){ this.buf=[]; this.org=''; this.lastMin=1; }, //get point is the only possibility, return the value or zero checkPoint:function(y,x,c){ var i,j,v,s,vs=matrixs.getPointVal(y,x); if (vs[_L]==1)return vs; for(i=0;i<vs[_L];i++){ v=vs.charAt(i); for(s=0,j=0;j<8;j++){ if(c.Ny[j].P[v])s++; if(s>0)break; } if(0==s)return v; for(s=0,j=0;j<8;j++){ if(c.Nx[j].P[v])s++; if(s>1)break; } if(0==s)return v; for(s=0,j=0;j<8;j++){ if(c.Nb[j].P[v])s++; if(s>0)break; } if(0==s)return v; } return 0 }, //infer values infer:function(){ var y,x,v,c,o=matrixs.O; for(y=1;y<=9;y++){ for(x=1;x<=9;x++){ c=o[y][x]; if(c.isFix)continue; v=this.checkPoint(y,x,c); if(0!=v){ debug.print(["point(",y,",",x,")=",v,"\t"].join('')); return matrixs.set(y,x,v,1); } } } return 0; }, doGuessFirst:function(){ //guess value struct {(y,x),v} var y,x,v,l,minX,minY,minL=10,Lm=this.lastMin,o=matrixs.O,c; for(y=1;y<=9;y++){ for(x=1;x<=9;x++){ //if isFix continue c=o[y][x]; if(c.isFix)continue; //get point value v=c.P.join(''); l=v[_L]; //find min value length Point if(l<minL){minX=x; minY=y; minL=l} if(Lm==l)break; } if(Lm==l)break; } this.lastMin=l; c=o[minY][minX]; var k,s,i,vn=[];minVs=c.P.join(''),minVn=99,Pointer=-1; //calculate each value's probability--- vn, & find the min value point for(k=0;k<minVs[_L];k++){ //get a value v=minVs.charAt(k); //calculat its nerb count for(s=0,i=0;i<20;i++) if(c.Na[i].P[v])s++; //save it vn[k]=s; //find the min value if(s<minVn){minVn=s; Pointer=k} } //return a guess point object return { x:minX, //point x y:minY, //point y v:minVs.charAt(Pointer),//i guess value//this is the max probability i:Pointer, //i guess value pointer vn:vn, //all point values nerb count av:minVs, //all point values r:matrixs.save() // save matrixs status } }, doGuessNext:function(gP){ //disable last guess point value gP.vn[gP.i]=99; //init value var s,gv={i:-1,vn:99},minVn=99,Pointer=-1; //find next value for(var k=0;k<gP.av[_L];k++){ s=gP.vn[k]; if(s<minVn){minVn=s; Pointer=k} } //no found return null if(-1==Pointer) return null; //update guess point value gP.v=gP.av.charAt(Pointer); gP.i=Pointer; return gP; }, //try to guess point value guess:function(gP){ //debug.printTitle('guess tree deep ==>',this.buf[_L]); //if exist guess point try next value if(gP){ //change guess point clean the error value gP=this.doGuessNext(gP); //if no value left null retrun ,do roll back if(null==gP){ //when error guess ,roll data back if(this.buf[_L]>0){ return this.guess(this.buf.pop()); } //no data to go back ,print error else{ debug.println("the input value is corrupted!"); return false; } } matrixs.load(gP.r,this.org); } //create a guess point else gP=this.doGuessFirst(); this.buf.push(gP); debug.print(["Guess(",gP.y,",",gP.x,")=",gP.v,"\t"].join('')); matrixs.set(gP.y,gP.x,gP.v,1); setTimeout(function(){intelligence.run()},10); //debug.stop(); }, //start function run:function(){ //check if the table is full filled if(matrixs.isFull()){ return debug.println("well done! ="+(new Date()-this.timer)); } //still some panes' value is unknown //hide the fellow logic stuct , the 'else' case is not necessary //else{ //check if any pane value is error if(matrixs.isError()){ //when error guess ,roll data back if(this.buf[_L]>0) return this.guess(this.buf.pop()); //no data to go back ,print error else return debug.println("the input value is corrupted!"); } //save curent status ,try to give one simple guess else{ //if infer valu is legal try to infer the next point value if(this.infer()) return setTimeout(function(){intelligence.run()},10); //can not infer any point value else return this.guess(); } }, start:function(){ this.timer=new Date(); this.reset(); this.org=matrixs.save(); this.run(); }},//debug functionsdebug={ //screen output device dev:null, //debug functions define here , init function will create button for these functions f:[], //initialization function , id - output device container id init:function(id){ this.dev=_F.$c('div'); _F.$a(_F.$(id),this.dev); for(var i=0;i<this.f[_L];i++)_F.$a(_F.$(id),_F.$c('input',{type:'button',value:this.f[i].n,onclick:this.f[i].f})); _F.$a(_F.$(id),_F.$c('input',{type:'button',value:'clear',onclick:function(){debug.clear()}})); }, //print information to debuger device print:function(){ _F.$a(this.dev,_F.$t(1==arguments[_L]?arguments[0]:Array.apply([],arguments))); this.dev.scrollTop+=200; }, //print information to debuger device end with crlf println:function(){ _F.$a(this.dev,_F.$t(1==arguments[_L]?arguments[0]:Array.apply([],arguments))); _F.$a(this.dev,_F.$c('br')); this.dev.scrollTop+=200; }, //print information to top document title printTitle:function(){top.document.title=(Array.apply([],arguments)).join(',').replace(/\s+/g,' ');}, //get input from user get:function(){return prompt(arguments[0],arguments[1])}, //clear debuge device ouput clear:function(){this.dev.innerHTML='';}, //stop running script by calling the native debuger if available, else do nothing stop:function(){debugger}}/*************************************************************//* this function draw all panes in the special id/* con1 container 1 id --left panes layer/* con2 container 2 id --right panes layer/* id1 choice table id --in left layer/* id2 main table id --contain ninety-nine panes /* id3 information table id string mark/*************************************************************/function DrawTables(con1,con2,id1,id2,id3){ var cont,tb,row,i,j,cell; cont=_F.$(con1); tb=_F.$c('table',{id:id1}); row=tb.insertRow(0); for(i=0;i<9;i++){row.insertCell(i).innerHTML=i+1} _F.$a(cont,tb); _F.$a(cont,_F.$c('hr')); tb=_F.$c('table',{id:id2}); for(i=0;i<9;i++){ row=tb.insertRow(i); for(j=0;j<9;j++){ cell=row.insertCell(j); cell.innerHTML=" "; cell.bgColor =((i>2&&i<6)^(j>2&&j<6))?"#ffffcc":"#ccffff"; } } _F.$a(cont,tb); cont.onselectstart=_F.f; cont=_F.$(con2); for(i=1;i<=9;i++){ tb=tb.cloneNode(true); tb.id=id3+i; _F.$a(cont,tb); } cont.onselectstart=_F.f; _F.$a(cont,_F.$c('div',{innerHTML:'<b>Copyright(C) 2008 BAREN Productions. <br />All rights reserved.</b>'}));}// global initialization funtion, create each object on document's Ready (function init(){ DrawTables('lp1','rp1','hx','tb',"de");delete DarwTables; ihx.Create('hx');delete ihx.Create; matrixs.Create('tb',"de");delete matrixs.Create; debug.init('debugWin');delete debug.init; _F.$l(document,function(){ var k=event.keyCode-48; if(k>0&&k<=9)ihx.click(k); //if(event.ctrlKey)debug.printTitle(matrixs.getCurPointInfo()); //debug.print(k); },"keydown"); setTimeout(function(){ _F.$h(_F.$('rp1')); matrixs.dump(); _F.$s(_F.$('rp1')); },10);})();//forbiden user select opration//document.onselectstart=_F.f;</script></html>