我已经编写了一个生成数独板的算法,但它失败了。我已经基于此编写了它,尽管它确实有所不同,因为在我偶然发现它之前我已经编写了很多代码。
编码
我设置了一个多维数组来保存名为matrix
. matrix
由 9 个数组组成,这些数组是行,每个数组包含 9 列。所以要获得第 4 行第 7 列的值,我会使用
matrix[3][6];
求解所有正方形的函数:
var populateMatrix = function() {
var possibles = generatePossibleNumbersArray();
var found = false;
for(var i=0; i< matrix.length; i++) {
for(var j=0; j< matrix[i].length; j++) {
while(possibles[i][j].length > 0) {
var rnd = Math.floor(Math.random() * possibles[i][j].length);
var num = possibles[i][j].splice(rnd, 1)[0];
if(isValid(i, j, num)) {
matrix[i][j] = num;
found = true;
break;
} else {
found = false;
continue;
}
}
if(!found) {
possibles[i][j] = [1,2,3,4,5,6,7,8,9];
j -= 2;
}
}
}
}
这generatePossibleNumbersArray()
只是一个用于创建多维数组的辅助函数,matrix
除了它被初始化为每个单元格保存一个整数 1-9 的数组。在populateMatrix()
函数期间,这些可能的数字会为每个单元格减少。
问题
它在每次完成矩阵之前都会失败,因为j
最终是-1
. 这是因为随着越来越多的单元格得到解决,算法会更难找到单元格的值,因此它会回溯。但它最终最终会一直回溯到j == -1
.
我真的认为这个算法会起作用,我花了一整天的时间试图解决这个问题,但我很困惑,所以任何人都可以对此有所了解,将不胜感激。
我想'我知道,我会写一个 javascript 函数来解决数独问题。它能有多难?'。我错了。
[解决方案]
基于@Steve314 的评论(他现在已被删除!)我添加matrix[i][j] = undefined
到算法中if(!found) { ...
,算法现在可以工作并且正在快速减轻。
如果有人感兴趣,这里是完整的代码。