当前位置: 代码迷 >> JavaScript >> javascript的数单独动填充算法代码
  详细解决方案

javascript的数单独动填充算法代码

热度:426   发布时间:2013-02-19 11:11:40.0
javascript的数独自动填充算法代码
  数独游戏的一段代码,忘记了用的是深度优先还是广度优先的搜索算法,使用了些概率上的算法改进,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>


  相关解决方案