首页 > 程序开发 > 软件开发 > Java >

Javascript实现数独算法

2016-12-17

最近一直在思考html5 的练手项目,奈何智商捉急,始终没有想好,无意间看到数独游戏,花了点小时间研究了一下,并不是说就一定会用html5去实现一个数独的小游戏,只是突然来了兴趣,也写了一个简单的数独算法,代码如下

最近一直在思考html5 的练手项目,奈何智商捉急,始终没有想好,无意间看到数独游戏,花了点小时间研究了一下,并不是说就一定会用html5去实现一个数独的小游戏,只是突然来了兴趣,也写了一个简单的数独算法,代码如下:

function generateArr() {
	var arr = [];
	for (var i = 0; i < 9; i++) {
		arr[i] = [];
		for (var j = 0; j < 9; j++) {
			arr[i][j] = 0;
		}
	}
	return arr;
}

/**
 * 获取n-m的随机整数
 * @param {} n
 * @param {} m
 * @return {}
 */
function random(n, m) {
	var c = m - n + 1;
	return Math.floor(Math.random() * c + n);
}

/**
 * 检测行是否符合标准
 * @param {} arr
 * @param {} row
 * @return {Boolean}
 */
function checkRow(arr, row) {
	for (var j = 0; j < 8; j++) {
		if (arr[row][j] == 0) {
			continue;
		}
		for (var k = j + 1; k < 9; k++) {
			if (arr[row][j] == arr[row][k]) {
				return false;
			}
		}
	}
	return true;
}

/**
 * 检测列是否符合标准
 * @param {} arr
 * @param {} col
 * @return {Boolean}
 */
function checkLine(arr, col) {
	for (var j = 0; j < 8; j++) {
		if (arr[j][col] == 0) {
			continue;
		}
		for (var k = j + 1; k < 9; k++) {
			if (arr[j][col] == arr[k][col]) {
				return false;
			}
		}
	}
	return true;
}

/**
 * 检测3X3是否符合标准
 * @param {} arr
 * @param {} row
 * @param {} col
 * @return {Boolean}
 */
function checkNine(arr, row, col) {
	// 获得左上角的坐标
	var j = Math.floor(row / 3) * 3;
	var k = Math.floor(col / 3) * 3;
	// 循环比较
	for (var i = 0; i < 8; i++) {
		if (arr[j + Math.floor(i / 3)][k + i % 3] == 0) {
			continue;
		}
		for (var m = i + 1; m < 9; m++) {
			if (arr[j + Math.floor(i / 3)][k + Math.round(i % 3)] == arr[j + Math.floor(m / 3)][k + Math.round(m % 3)]) {
				return false;
			}
		}
	}
	return true;
}

/**
 * 检查对角线是否符合标准(左上->右下)
 * @param {} arr
 * @param {} row
 * @param {} col
 */
function checkDiagonalLeftToRight(arr, row, col) {
	if (row != col) {
		return true;
	}
	for (var i = 0; i < 8; i++) {
		if (i == row) {
			continue;
		}
		if (arr[i][i] == arr[row][col]) {
			return false;
		}
	}
	return true;
}

/**
 * 检查对角线是否符合标准(右上->左下)
 * @param {} arr
 * @param {} row
 * @param {} col
 */
function checkDiagonalRightToLeft(arr, row, col) {
	if ((row + col) != 8) {
		return true;
	}
	for (var i = 0; i < 8; i++) {
		if (i == row) {
			continue;
		}
		if (arr[i][8 - i] == arr[row][col]) {
			return false;
		}
	}
	return true;
}

/**
 * 是否满足行、列和3X3区域不重复的要求
 * @param {} arr
 * @param {} row
 * @param {} col
 * @return {}
 */
function isCorret(arr, row, col) {
	return (checkRow(arr, row) && checkLine(arr, col) && checkNine(arr, row, col));
}

/**
 * 生成1-9的随机整数
 * @return {}
 */
function generateRandom() {
	return Math.floor(Math.random() * 9 + 1);
}

function generateShuDu() {
	var arr = generateArr();
	for (var i = 0; i < 9; i++) {
		var time = 0;
		for (var j = 0; j < 9; j++) {
			arr[i][j] = time == 9 ? 0 : generateRandom();
			if (arr[i][j] == 0) {// 不是第一列,则倒退一列
				if (j > 0) {
					j -= 2;
					continue;
				}
				else {// 是第一列,则倒退到上一行的最后一列
					i--;
					j = 8;
					continue;
				}
			}
			if (isCorret(arr, i, j)) {
				time = 0;// 初始化time,为下一次填充做准备
			}
			else {
				time++;// 次数增加1
				j--;// 继续填充当前格
			}
		}
	}
	var result = "";
	for (var i = 0; i < 9; i++) {
		for (var j = 0; j < 9; j++) {
			result += arr[i][j];
		}
		result += "\n";
	}
	console.log(result);
}
这里面虽然加了两个检查对角线的方法,但是可能是考虑不周全吧,一加上对角线的检查,程序就卡死了,所以上述代码仅仅是实现最简单的数独,并非是对角线数独,在实现该算法的时候采用的是最简单的一个个单元格填充的方式,并没有顾全性能等,如有幸有大神看到,还望不吝赐教!

最后附一张结果图:


\

相关文章
最新文章
热点推荐