JavaScript 数独网格生成不会一直执行

Question

所以我一直试图在JavaScript中生成一个解决的数独网格一段时间了。我现在有了一个运行平稳的版本，直到某个(总是不同的)点。我没有得到任何错误，但在某些时候，下面的函数只是停止执行，我不明白为什么。

我的源代码:

//* HELPER FUNCTION FISHER-YATES SHUFFLE FOR ARRAYS
//* USE: shuffle(arr);
function shuffle(array) {
let currentIndex = array.length, randomIndex;
// While there remain elements to shuffle.
while (currentIndex != 0) {
// Pick a remaining element.
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex--;
// And swap it with the current element.
[array[currentIndex], array[randomIndex]] = [
array[randomIndex], array[currentIndex]];
}
return array;
}
//* HELPER FUNCTION get number in Range 0 and 8
function getRandomInRange() {
return Math.random() * (8 - 0) + 0;
}

我实现了fisher yates shuffle，因为它似乎与python中使用的python数组shuffle方法相同。

let grid = [
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
]
let row;
let col;
let numberList = [1, 2, 3, 4, 5, 6, 7, 8, 9];

以上是所有使用的全局变量。

//A function to check if the grid is full
function checkGrid() {
for (let i = 0;i < 9;i++) {
for (let j = 0;j < 9;j++) {
if (grid[i][j] === 0) {
//The grid is not full
return false
}
}
}
//The grid is complete
return true
}

上面的函数检查数独网格中是否还有一个0

下面是逐个值填充网格的函数。这个函数在某个点停止执行。这可能是JavaScript本身的问题，因为递归，或者这是一个错误的代表我?

function fillGrid() {
//let counter;
for (let i = 0;i < 81;i++) {
row = Math.floor(i / 9);
col = i % 9;
if (grid[row][col] === 0) {
//console.log(row + "/" + col);
shuffle(numberList);
numberList.forEach(v => {
//Check that this value has not already been used on this row
if (!grid[row].includes(v)) {
//Check that this value has not already been used on this column
if (grid[0][col] !== v &&
grid[1][col] !== v &&
grid[2][col] !== v &&
grid[3][col] !== v &&
grid[4][col] !== v &&
grid[5][col] !== v &&
grid[6][col] !== v &&
grid[7][col] !== v &&
grid[8][col] !== v
) {
//Identify which of the 9 squares we are working on
let square = [];
if (row < 3) {
if (col < 3) {
for (let x = 0;x < 3;x++) {
square.push(grid[x].slice(0, 3));
}
}
else if (col < 6) {
for (let x = 0;x < 3;x++) {
square.push(grid[x].slice(3, 6));
}
}
else {
for (let x = 0;x < 3;x++) {
square.push(grid[x].slice(6));
}
}
}
else if (row < 6) {
if (col < 3) {
for (let x = 3;x < 6;x++) {
square.push(grid[x].slice(0, 3));
}
}
else if (col < 6) {
for (let x = 3;x < 6;x++) {
square.push(grid[x].slice(3, 6));
}
}
else {
for (let x = 3;x < 6;x++) {
square.push(grid[x].slice(6));
}
}
}
else {
if (col < 3) {
for (let x = 6;x < 9;x++) {
square.push(grid[x].slice(0, 3));
}
}
else if (col < 6) {
for (let x = 6;x < 9;x++) {
square.push(grid[x].slice(3, 6));
}
}
else {
for (let x = 6;x < 9;x++) {
square.push(grid[x].slice(6));
}
}
}
//Check that this value has not already been used on this 3x3 square
if (!square[0].includes(v) &&
!square[1].includes(v) &&
!square[2].includes(v)
) {
grid[row][col] = v;
if (checkGrid()) {
return true
} else {
if (fillGrid()) {
return true
}
}
}
}
}
});
break
}
}
grid[row][col] = 0;
}
//generate a fully solved grid
fillGrid();
grid.forEach(x => console.log(x));

无论如何，如果我在node或chrome中运行它，使用或不使用调试工具，我都不会实现完全填充的网格。例子结果:

(9) [9, 4, 7, 5, 1, 6, 8, 3, 2]
(9) [3, 5, 6, 4, 8, 9, 1, 7, 0]
(9) [0, 0, 0, 0, 0, 0, 0, 0, 0]
(9) [0, 0, 0, 0, 0, 0, 0, 0, 0]
(9) [0, 0, 0, 0, 0, 0, 0, 0, 0]
(9) [0, 0, 0, 0, 0, 0, 0, 0, 0]
(9) [0, 0, 0, 0, 0, 0, 0, 0, 0]
(9) [0, 0, 0, 0, 0, 0, 0, 0, 0]
(9) [0, 0, 0, 0, 0, 0, 0, 0, 0]

或

(9) [6, 1, 3, 9, 4, 5, 7, 8, 2]
(9) [4, 8, 9, 2, 6, 7, 5, 3, 1]
(9) [7, 2, 5, 3, 1, 8, 6, 9, 4]
(9) [3, 7, 2, 5, 9, 6, 8, 1, 0]
(9) [0, 0, 0, 0, 0, 0, 0, 0, 0]
(9) [0, 0, 0, 0, 0, 0, 0, 0, 0]
(9) [0, 0, 0, 0, 0, 0, 0, 0, 0]
(9) [0, 0, 0, 0, 0, 0, 0, 0, 0]
(9) [0, 0, 0, 0, 0, 0, 0, 0, 0]

Answer 1

[3, 8, 4, 1, 6,2, 9, 5, 7],
[6, 5, 2, 9, 7,3, 4, 8, 1],
[7, 9, 1, 4, 5,8, 6, 3, 2],
[4, 6, 3, 5, 9,7, 8, 1, 0],
[0, 0, 0, 0, 0,0, 0, 0, 0],
[0, 0, 0, 0, 0,0, 0, 0, 0],
[0, 0, 0, 0, 0,0, 0, 0, 0],
[0, 0, 0, 0, 0,0, 0, 0, 0],
[0, 0, 0, 0, 0,0, 0, 0, 0]

我在第4行得到了错误。您的脚本必须设置一个2，但不能设置它，因为它已经存在于这些列中。你必须编写一个函数来处理发生冲突的事件。