数独游戏的一段代码，忘记了用的是深度优先还是广度优先的搜索算法，使用了些概率上的算法改进，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 filled
intelligence={
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 functions
debug={
//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>