`
yiminghe
  • 浏览: 1460018 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

编程之美:javascript的数独实现

阅读更多

书中没有给出具体实现,但是算法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>
  • 大小: 7.6 KB
0
0
分享到:
评论

相关推荐

    JavaScript数独游戏.zip

    JavaScript数独游戏是一种基于网页的互动游戏,利用JavaScript编程语言实现。JavaScript是一种广泛应用于Web开发的脚本语言,它在浏览器端运行,为用户提供动态、交互式的网页体验。在这个数独游戏中,用户可以在...

    数独游戏通过JavaScript技术实现向TypeScript技术实现的转换

    本项目探讨的是将一个使用JavaScript实现的数独游戏转换为TypeScript的过程,这是一种从弱类型到强类型的语言迁移,旨在提升代码的稳定性和可维护性。 JavaScript是动态类型的脚本语言,而TypeScript是它的超集,...

    JS数独 v1.0.2

    《JS数独 v1.0.2》是一款基于JavaScript实现的数独小游戏,适用于现代浏览器,尤其是基于WebKit内核的浏览器如Chrome或Safari。在IE浏览器中,部分验证功能可能无法正常工作,但不影响基本的游戏体验。这个项目展示...

    js版数独游戏 智力小游戏

    在本项目中,我们讨论的是JavaScript实现的数独游戏。JavaScript是一种常用的编程语言,常用于网页和浏览器交互,也适用于开发各种类型的游戏。在这个js版数独游戏中,开发者利用JavaScript的特性创建了一个交互式的...

    微信小程序源码:数独小游戏.rar

    - 逻辑算法:实现数独的填充逻辑,包括合法性检查(每行、每列、每个宫格内数字是否唯一)、递归填充等。 - UI交互:用户输入数字、清除、提示等功能的实现,需要结合WXML和JavaScript进行事件绑定。 - 状态管理:...

    精选_基于JavaScript实现的数独游戏_源码打包

    在这个“精选_基于JavaScript实现的数独游戏_源码打包”中,我们将深入探讨如何使用JavaScript这一强大的客户端开发语言来创建一个互动式的数独游戏。 首先,我们需要理解JavaScript的基础语法和DOM操作。...

    数独计算器(HTML+JavaScript)

    "数独计算器(HTML+JavaScript)"是一个利用网页技术实现的数独解算程序,它允许用户在网页上填写数独网格,并通过JavaScript进行计算。 首先,我们来看HTML部分。HTML(超文本标记语言)是构建网页的基础,它定义了...

    javascript实现数独解法

    在编程实现数独解法时,通常会涉及到一些特定的算法,其中一种常见的方法是使用回溯算法,还有一种是基于位运算的算法。下面详细说明javascript实现数独解法中的关键知识点。 ### 初始化数独游戏板 在JavaScript中...

    sudoku:JavaScript 中的简单数独游戏

    在这个特定的项目中,“sudoku:JavaScript 中的简单数独游戏”是一个利用JavaScript实现的数独游戏。 JavaScript是一种广泛用于网页和互联网应用的编程语言,它允许开发者在客户端进行动态内容的创建。在这个项目中...

    Sudoku_App:经典数独拼图应用

    9. **模块化编程**:现代JavaScript开发常采用模块化,例如使用ES6的import/export语法,将代码拆分为可重用的组件,提高代码组织性和可维护性。 10. **性能优化**:对于大型数独网格,应用可能使用事件委托来减少...

    sudoku:创建数独游戏和求解器

    通过以上步骤,我们可以构建一个完整的JavaScript数独游戏应用,包括生成器和求解器。这个项目不仅涵盖了基本的JavaScript编程技巧,还涉及到了数据结构、算法以及用户交互设计等多个方面,对于提升编程技能是非常有...

    Sudoku:用Javascript制作的简单数独

    在这个“Sudoku:用Javascript制作的简单数独”项目中,我们将探讨如何利用JavaScript语言实现一个基本的数独游戏。 首先,我们需要理解项目的结构。"Sudoku-master"可能是一个Git仓库的名称,通常包含项目源代码、...

    jsSudoku:浏览器数独游戏-开源

    jsSudoku是一款以JavaScript实现的开源数独游戏,它的出现不仅提供了一种在线娱乐方式,也为开发者和编程学习者提供了宝贵的资源。开源性质使得这个游戏具备了持续改进和创新的可能性,同时也促进了技术分享和社区...

    js数独游戏 v1.0.1

    《JavaScript实现的数独游戏 v1.0.1》 数独是一种广受欢迎的逻辑解谜游戏,它基于一个9x9的网格,分为9个3x3的小宫格。玩家的目标是根据给出的部分数字填充空白格子,使得每一行、每一列以及每个小宫格内的数字从1...

    递归回溯算法破解数独

    在这个项目中,使用JavaScript作为编程语言,这是因为JavaScript在网页开发中非常常见,且可以方便地实现交互式界面。用户可以自定义数独题目,程序将利用递归回溯算法快速或可视化地解决这些题目。 在"index.html"...

    sudoku-js:JavaScript 中的数独求解器

    在这个项目中,我们探讨的是一个名为“sudoku-js”的JavaScript实现,它是一个专门用于解决数独谜题的库。JavaScript作为一种广泛应用于前端开发和服务器端的编程语言,非常适合创建这种交互式的游戏或工具。 首先...

    数独:数独的php实现

    在这个“数独:数独的PHP实现”主题中,我们将探讨如何使用PHP编程语言来创建一个能够生成、解决和验证数独谜题的系统。 首先,我们需要理解数独的基本数据结构。在PHP中,我们可以使用二维数组来表示9×9的数独...

    解答数独、自定义手动输入数独题目。快速生成数独答案。

    本话题涉及的知识点主要集中在JavaScript编程语言上,用于实现数独的解答和自定义题目的生成。 一、数独解法算法 1. 基于回溯的深度优先搜索(DFS):这是一种典型的递归方法,从空格最多的单元格开始尝试填入数字...

    JS实现数独求解算法

    这个过程可以通过编程来实现,本例中我们将探讨如何使用JavaScript来实现数独的求解算法。 首先,我们需要理解数独的特性,即每个单元格的候选数集合。在数独的初始状态下,部分单元格已经填有数字,而其余单元格则...

    sudoku-solver:解决数独

    该项目包含两个版本的数独解算器:一个使用Python编程语言实现,另一个使用JavaScript。这两种语言各有特点,Python以其简洁明了的语法和丰富的库支持在数据分析和算法实现上广受青睐,而JavaScript作为前端开发的...

Global site tag (gtag.js) - Google Analytics