编程之美：javascript的数独实现

yiminghe

浏览: 1431447 次
性别:
来自: 上海

最近访客更多访客>>

akingde

xmg25

xiaolan02

archerfrank

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

algorithm

编程 JavaScript J#prototype Cache

书中没有给出具体实现，但是算法1也不难，自己实现玩玩用来测智商吧。

规则：

一个由3个3*3的子矩阵组成的9*9矩阵，其中每个3*3矩阵都由1-9这9个数字组成，且数独矩阵中每行每列都没有重复数字。

3*3子矩阵数字各不相同

效果图：

演示@google code

代码： （可copy直接运行，或附件）

1.0 (2009-07-22 16:54)

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="zh-CN" dir="ltr">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<title>数独游戏</title>

<script type="text/javascript">

//<![CDATA[

 /***
	
		产生一个 9*9 的数独矩阵，满足数独规则 :
		
		1.一个由9个3*3的子矩阵组成的9*9矩阵，其中每个3*3矩阵都由1-9这9个数字组成，
		
		2.且数独矩阵中每行每列都没有重复数字。
		
		
		关键方法：
		深度搜索，记下每个单元格对应的可选数序列，当没有路线时清空自己的可选数序列,
		利用回朔，改变上个单元格已选泽的值
		
		
	
	
	****/
	
	
	
	
	
	
	
	
	if(!Array.prototype.indexOf) {  
	   Array.prototype.indexOf = function(v){  
	        for(var i=0;i<this.length;i++)  
	            if(this[i] === v) return i;  
	        return -1;  
	    }  
	}  
//http://blog.stevenlevithan.com/archives/faster-trim-javascript
//fast !
	if(!String.prototype.trim) { 
			String.prototype.trim=function() {
	                      var	str = this.replace(/^\s\s*/, ''),
		              ws = /\s/,
		               i = str.length;
	                       while (ws.test(str.charAt(--i)));
	                       return str.slice(0, i + 1);
                          }
	}
	
	
       
	/*
		*********************************************************************
		start : 数组随机函数组
	
		floy 算法对数组进行重排序
		http://yiminghe.iteye.com/blog/409039
	*/

  function randIt(l,u){  
       return l+Math.floor(Math.random()*(u-l+1));  
  }
  
  
  /* 
       1 - n 中随机取m个数组成序列 
   */  
   function randomList(m,n) {  
       var start=n-m+1;  
       var holder=[];  
         
       for(var i=start;i<=n;i++) {  
           //random 1~i not 1~i-1  
           var cur=randIt(1,i);  
           //trick tick  
           var position=holder.indexOf(cur)+1;       
           var insert=position?i:cur;  
           holder.splice(position,0,insert);                 
       }  
         
       return holder;  
    }
   
   
   /**
   	arr 数组元素随机打乱
   **/
   function randomArray(arr) {
  		var rIndex=randomList(arr.length,arr.length);
  		var newArr=[];
  		for(var i=0;i<rIndex.length;i++) {
  			newArr[i]=arr[rIndex[i]-1];
  		}
  		return newArr;
  		
   }
   
/*
	end : 数组随机函数组
	********************************************************************************
*/   
   
   
 
	/*
		数独 core 对象 ,其实就是对2维数组的封装
	*/ 
	function Sudoku(){	
	
	}  


   
       

	/*
		得到当前单元格的一个可选值，-1 表示没有可选值了，要向前回朔
	*/
	Sudoku.prototype.getNextRandom = function(currentCell){		
		
		var currentX=currentCell%9; //col
		var currentY=Math.floor(currentCell/9); //row
		var currentSubMaxtrixX=Math.floor(currentX/3); //sub this.matrix col
		var currentSubMaxtrixY=Math.floor(currentY/3); //sub this.matrix row
		var index=0;
		
		//初始可选数字
		var avails=[1,2,3,4,5,6,7,8,9];		
		
		//没有计算过，计算可选序列，用于回朔枚举
		if(!this.matrix[currentY][currentX]) {			
			
			/*
				根据数独规则进行过滤
			*/
			
			//同一行不能重复
			for(var i=0;i<currentX;i++) {
				if(avails.indexOf(this.matrix[currentY][i].value)!=-1)
					avails.splice(avails.indexOf(this.matrix[currentY][i].value),1);
			}
			
			//同一列不能重复
			for(var i=0;i<currentY;i++) {
				if(avails.indexOf(this.matrix[i][currentX].value)!=-1)
					avails.splice(avails.indexOf(this.matrix[i][currentX].value),1);
			}
			
			//3*3 小矩阵不能重复
			outer:for(var j=currentSubMaxtrixY*3;j<currentSubMaxtrixY*3+3;j++) {		
				for(var i=currentSubMaxtrixX*3;i<currentSubMaxtrixX*3+3;i++) {
					
					//小矩阵验证到当前单元格就行了
					if(j==currentY && i==currentX) break outer;			
					
					if(avails.indexOf(this.matrix[j][i].value)!=-1)
						avails.splice(avails.indexOf(this.matrix[j][i].value),1);
				}
			}
			
			//没有选择了
			if(avails.length==0) return  -1;
			
			//avails 最好随机打乱，每次生成不同的数独
			avails=randomArray(avails);
			
		} else {
			
			index=this.matrix[currentY][currentX].index;
			
			//枚举完毕，仍然不行，清除计算状态，
			if(index == this.matrix[currentY][currentX].availList.length-1) {
				this.matrix[currentY][currentX]=null;
				return -1;
			}
			
			//回朔到这里了，当前数字不行，那么在可选序列中选中下一个可选数字
			++index;
			avails=this.matrix[currentY][currentX].availList;
				
		}
		
		//返回数独单元的结构表示
		return {
			//当前单元格选择的值的index
			index:index,
			//记下产生的可选序列，回朔时用于枚举下一个值
			availList:avails,
			value:avails[index]
		};
		
	}
	
	
	/*
		指定编号的 Cell 设置数值
	*/
	Sudoku.prototype.setValueOfMatrix = function(currentCell,val) {
		var currentX=Math.floor(currentCell%9); //col
		var currentY=Math.floor(currentCell/9); //row
		this.matrix[currentY][currentX]=val;
	}
	
	
	/*
		静态方法：验证是否符合数独规则
	*/
	Sudoku.validate = function (matrix){
		var cache={};
		
		for(var i=0;i<9;i++) {
			cache={};
			for(var j=0;j<9;j++) {
				if(cache[matrix[i][j]]) {
					
					return "row "+(i+1)+"  error";	
				}		
				cache[matrix[i][j]] = 1;
			}
		}	
		
		
		for(var i=0;i<9;i++) {
			cache={};
			for(var j=0;j<9;j++) {
				if(cache[matrix[j][i]]) {
					
					return "col "+(j+1)+"  error";
				}	
				cache[matrix[j][i]] = 1;
			}
		}	
		
		
		for(var i=0;i<3;i++) {
			
			for(var j=0;j<3;j++) {
				
				cache={};
				
				for(var subi=i*3;subi<i*3+3;subi++) {
					
					for(var subj=j*3;subj<j*3+3;subj++) {
						
						if(cache[[matrix[subi][subj]]]) {
							
							return "submatrix "+(i*3+j)+"error";
						}
						cache[matrix[subi][subj]] = 1;
				
					}	
					
				
				}	
					
			}
		}	
		return null;		
	}
	
	
	/*
		重要，生成符合数独规则的矩阵
	*/
	Sudoku.prototype.generate = function (space) {
		this.matrix=[];
		
		for(var i=0;i<9;i++) 
			this.matrix.push([]);			
		
		var currentCell=0;
		
		//按照行编号 0~80 ,共 9*9=81 个单元格
		while(true) {
			var nextValue=this.getNextRandom(currentCell);			
			if(nextValue!=-1) {
				this.setValueOfMatrix(currentCell,nextValue);
				++currentCell;
			} else {
				//无值可选了，回朔
				--currentCell;	
			}
			
			//9*9 全部完成
			if(currentCell==81) break;
		}
		
		
		
		/*
			矩阵已经搞好了--------------------------------------------
		*/ 
					
		var holes=randomList(space,81);
		
		for(var i=0;i<holes.length;i++) {
			var currentX=Math.floor((holes[i]-1)%9); //col
			var currentY=Math.floor((holes[i]-1)/9); //row
			this.matrix[currentY][currentX]=null;
		}
		
		return this.matrix;		
		
	}
	 //]]>

</script>





<style type="text/css">
	table {
		border-collapse: collapse;
		width: 80%;
		padding-left: 5%;
		table-layout: fixed;
		margin: 20px;
	}
	
	div {
		margin: 20px;
		padding-left: 5%;
	}
	
	input#space {
		margin-right: 10px;
	}
	
	td {
		padding: 5px;
		border: 1px solid black;
	}
	
	input.tableCell {
		width: 80%;
	}
</style>
</head>
<body>
	<table cellspacing="0" cellpadding="0">
		<caption>我的数独</caption>
		<tbody id="dataTable">
			<tr>
				<td>1</td>
				<td>1</td>
				<td>1</td>
				<td>1</td>
				<td>1</td>
				<td>1</td>
				<td>1</td>
				<td>1</td>
				<td>1</td>
			</tr>
		</tbody>
	
	</table>
	<div>
		<label for="space">空格数：</label> 
		<input type="text" id="space"	size="2" value="2" /> 
		<input type="button" value="生成数独" id="run" /> 
		<input type="button" value="我要验证" id="validate"	/>
		
	</div>
	<script type="text/javascript">
		//<![CDATA[	
	
		function collectData(tableEl){
			var matrix=[];
			for(var i=0;i<tableEl.childNodes.length;i++) {
				
				var tr=tableEl.childNodes[i].childNodes;
				var row=[];
				for(var j=0;j<tr.length;j++) {
					var td=tr[j];
					
					var ti=0;
					
					while(td.childNodes[ti] && td.childNodes[ti].nodeType ==3 )ti++;
					
					if(td.childNodes[ti]) {
												
						if( ! /^[1-9]$/.test(td.childNodes[ti].value.trim())) {
							return "输入1-9之间";
						}				
						
						row.push(parseInt(td.childNodes[ti].value.trim()));
					}
					
					else {
						row.push(parseInt(td.innerHTML));
					}
					
				}
				
				matrix.push(row);
				
			}		
			
			return matrix;
		
		}
		
		
		
		function startValidate(){
			var dataTable=document.getElementById("dataTable");
			var newMatrix = collectData(dataTable);
			if(typeof newMatrix == "string") {
				alert(newMatrix);
				return;
			}
			
			var info=Sudoku.validate(newMatrix);
			if(info)
				alert(info);
			else
				alert("恭喜你，成功了");
		}
		
		
		
		/*
			*****************************************************
			启动函数来了：
			
		*/
		function main(){
		
			var space =parseInt(document.getElementById("space").value);
			
			if(isNaN(space))
				space=0;
			
			if(space>81 || space<0) {
				alert("空格数不合规范:(");
				return;
			}
			
			var sudoku = new Sudoku();
			var matrix= sudoku.generate(space);
			
			var dataTable=document.getElementById("dataTable");
			
			
			
			while (dataTable.childNodes[0]) {
				dataTable.removeChild(dataTable.childNodes[0]);
			}
			
			for(var i=0;i<9;i++) {
				var dataTableTr=document.createElement("tr");
				for(var j=0;j<9;j++) {
					var dataTableTd=document.createElement("td");
					
					if(matrix[i][j])
						dataTableTd.innerHTML=matrix[i][j].value;
					else
						dataTableTd.innerHTML="<input type='text' class='tableCell' />";
						
					dataTableTr.appendChild(dataTableTd);
					//document.writeln(matrix[i][j].value+"&nbsp;");
				}
				dataTable.appendChild(dataTableTr);
			}
			
			
		}
		main();
		
		document.getElementById("run").onclick=function(){
			main();
		};
		
		document.getElementById("validate").onclick=function(){
			startValidate();
		};
		//]]>
		 
	</script>
</body>
</html>

Sudoku_1.0.zip (3.8 KB)
下载次数: 56

查看图片附件

0
顶

0
踩

分享到：

Extjs3.0 DomHelper Bug | 编程之美:烙饼排序问题

2009-07-22 15:46
浏览 4929
评论(0)
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

编程之美：javascript的数独实现

评论

发表评论

相关推荐

最近访客 更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论

编程之美：javascript的数独实现

评论

发表评论

相关推荐

构建前端 DSL

circular dependency

write html parser

转载：瀑布流布局浅析

循环引用下的深度克隆

开关状态信息的保存

LL文法算法-1

NFA到DFA的转换演示

gzip压缩实现注意

三点共线判断

多维数组迭代器应用

google 开源项目

大数据量，海量数据 处理方法总结

Bloom Filter Technical Report

找零问题

背包问题javascript演示

hanoi问题求解

后缀表达式的javascript转化演示

LCA In Javascript 演示

Array.prototype.sort 稳定性问题

最近访客更多访客>>

大数据量，海量数据处理方法总结