JavaScript九宫格数独生成算法

将乐信息网 http://www.jianglexinxi.cn 2020-09-17 10:18 出处:网络
九宫格数独,JavaScript九宫格数独生成算法 前几天突然想写一个数独游戏。本来以为没什么难度。结果实现起来还是花了一点功夫。要做数据游戏,并不是随意地在九宫格里放一些数字让玩家来填写。一是你得保证你放的数字

九宫格数独,JavaScript九宫格数独生成算法

前几天突然想写一个数独游戏。本来以为没什么难度。结果实现起来还是花了一点功夫。要做数据游戏,并不是随意地在九宫格里放一些数字让玩家来填写。一是你得保证你放的数字符合数独的规则。二是你得保证你的数独是有解的。

所以在开始一局数独游戏之前,你要生成一个完整的数独,然后从中扣掉一些数字。让用户来填写。


数独规则:

数独(すうどく,Sūdoku),是源自18世纪瑞士发明,流传到美国,再由日本发扬光大的一种数学游戏。是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫内的数字均含1-9,不重复。 数独盘面是个九宫,每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件,利用逻辑和推理,在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次,所以又称“九宫格”。


本文介绍生成数独的算法。


先来一个九宫格的图,方便看着它思考。

JavaScript九宫格数独生成算法


一共九九八十一个格子,算法主要思路。为每一个格子填上一个符合数独条件的值。

数组以左上角为圆点,横为x轴,竖为y轴  在数组中对应的下标为:


11  21  31      41  51  61      71  81  91
12  22  32      42  52  62      72  82  92
13  23  33      43  53  63      73  83  93

14  24  34      44  54  64      74  84  94  
15  25  35      45  55  65      75  85  95  
16  26  36      46  56  66      76  86  96

17  27  37      47  57  67      77  87  97  
18  28  38      48  58  68      78  88  98  
19  29  39      49  59  69      79  89  99  


随机生成一个值填入数组。  

随机生成下一个值。判断不在数组中其所在横、竖、三宫格对应的下标里。获取横、竖、三宫的的下标使用过的值,算其可用的数字。随机取可用数字中的一个。如果没有可用数字,本次循环失败,回到开始重新算。

循环生成下一个值

……

直到81个下标位置都有符合条件的值。数独数组就生成完毕了!


然后我做了一点优化:

其实对于最开始的一些值,可以不用判断那么多,只需要把1-9乱序,依次放入九个格子中去。 我的做法是先在对角线上的三宫乱序依次放入1-9。就可以只用很少的计算量得出来27个值。因为对角线上填的值,不会互相影响。没有横竖的影响。

JavaScript九宫格数独生成算法


生成了这27个值之后,再使用上面的算法来计算,计算量少了不少,计算效率和成功率就大了很多了。


随机测试了几次,看我console出来的结果:

数独生成完毕,耗时:0.972秒!

数独生成完毕,耗时:0.081秒!

数独生成完毕,耗时:1.305秒!

数独生成完毕,耗时:0.102秒!

数独生成完毕,耗时:0.065秒!

数独生成完毕,耗时:0.813秒!

……

还是不算慢吧。


核心代码,从完整的里面扣出来的:

	createSdArr:function(){
		//生成数独数组。
		var that = this;
		try{
			this.sdArr = [];
			this.setThird(2,2);
			this.setThird(5,5);
			this.setThird(8,8);
			var allNum = [1,2,3,4,5,6,7,8,9];
			outerfor:
			for(var i=1;i<=9;i++){
				innerfor:
				for(var j=1;j<=9;j++){
					if(this.sdArr[parseInt(i+''+j)]){
						continue innerfor;
					}
					var XArr = this.getXArr(j,this.sdArr);
					var YArr = this.getYArr(i,this.sdArr);
					var thArr = this.getThArr(i,j,this.sdArr);
					var arr = getConnect(getConnect(XArr,YArr),thArr);
					var ableArr = arrMinus(allNum,arr);

					if(ableArr.length == 0){
						this.createSdArr();
						return;
						break outerfor;
					}

					var item;
					//如果生成的重复了就重新生成。
					do{
						item = ableArr[getRandom(ableArr.length)-1];
					}while(($.inArray(item, arr)>-1));

					this.sdArr[parseInt(i+''+j)] = item;
				}
			}
			this.backupSdArr = this.sdArr.slice();
		}catch(e){
			//如果因为超出浏览器的栈限制出错,就重新运行。
			that.createSdArr();
		}
	},
	getXArr:function(j,sdArr){
		//获取所在行的值。
		var arr = [];
		for(var a =1;a<=9;a++){
			if(this.sdArr[parseInt(a+""+j)]){
				arr.push(sdArr[parseInt(a+""+j)])
			}
		}
		return arr;
	},
	getYArr:function(i,sdArr){
		//获取所在列的值。
		var arr = [];
		for(var a =1;a<=9;a++){
			if(sdArr[parseInt(i+''+a)]){
				arr.push(sdArr[parseInt(i+''+a)])
			}
		}
		return arr;
	},
	getThArr:function(i,j,sdArr){
		//获取所在三宫格的值。
		var arr = [];
		var cenNum = this.getTh(i,j);
		var thIndexArr = [cenNum-11,cenNum-1,cenNum+9,cenNum-10,cenNum,cenNum+10,cenNum-9,cenNum+1,cenNum+11];
		for(var a =0;a<9;a++){
			if(sdArr[thIndexArr[a]]){
				arr.push(sdArr[thIndexArr[a]]);
			}
		}
		return arr;
	},
	getTh:function(i,j){
		//获取所在三宫格的中间位坐标。
		var cenArr = [22,52,82,25,55,85,28,58,88];
		var index = (Math.ceil(j/3)-1) * 3 +Math.ceil(i/3) -1;
		var cenNum = cenArr[index];
		return cenNum;
	},
	setThird:function(i,j){
		//为对角线上的三个三宫格随机生成。
		var numArr = [1,2,3,4,5,6,7,8,9];
		var sortedNumArr= numArr.sort(function(){return Math.random()-0.5>0?-1:1});
		var cenNum = parseInt(i+''+j);
		var thIndexArr = [cenNum-11,cenNum-1,cenNum+9,cenNum-10,cenNum,cenNum+10,cenNum-9,cenNum+1,cenNum+11];
		for(var a=0;a<9;a++){
			this.sdArr[thIndexArr[a]] = sortedNumArr[a];
		}
	}


生成的完整数独是这样:

JavaScript九宫格数独生成算法



这篇就介绍这么多。欢迎留言交流。

也可以自己去试玩下这个数独:

http://runningls.com/demos/2016/soduku/

看完整代码可以到我的github。

https://github.com/liusaint/games/tree/master/soduku

最近刚开始弄的,五月份要去上海找工作了,要show code了啊。



生成数独数组之后,后续工作是从中扣除一定数量的值,然后让用户填写。

然后检测用户输入是不是符合数独规则。(并不是直接和我们生成的数组对比,考虑到可能有不同的解法。)

另外解数独跟生成数独的方法也是差不多的。


转载请注明出处:http://blog.csdn.net/liusaint1992/article/details/51147149 因为文章可能会修改。

JavaScript九宫格数独生成算法的相关内容如下:

本文标题:JavaScript九宫格数独生成算法
http://www.jianglexinxi.cn/yanergaozhi/481773.html

0

精彩评论

暂无评论...
验证码 换一张
取 消