我不知道我的第一个while循环出了什么问题。break语句有问题吗？我的逻辑有问题吗？
无限期运行：
function solve(board) {
board = parseBoard(board);
let holes = getEmpties(board);
let i = 0;
let l = holes.length;
let counter = 1;
while (i < l) {
let hole = holes[i];
let row = hole[0];
let column = hole[1];
let n = board[row][column] + 1;
console.log(counter ++); // over 10000 and still going
while(n < 10) {
if (check(board, row, column, n)) {
// check if in the same row, column, 3*3 square has the same
// value "n", return true if all 3 of them have no such value.
// store solution
board[row][column] = n;
i ++;
break;
} else if (n === 9) {// checked all 9 values
// reset value
board[row][column] = 0;
i --;
}
n ++;
}
}
return board;
}
运行良好：
function solve(board) {
board = parseBoard(board);
let holes = getEmpties(board);
let i = 0;
let l = holes.length;
let counter = 1;
while (i < l) {
let found = false;
let hole = holes[i];
let row = hole[0];
let column = hole[1];
let n = board[row][column] + 1;
console.log(counter ++); // running 2203 times
while(!found && n < 10) {
if (check(board, row, column, n)) {
found = true;
board[row][column] = n;
i ++;
} else {
n ++;
}
}
if (!found) {
board[row][column] = 0;
i --;
}
}
return board;
}
澄清：
这是标准的9*9数独游戏。
解析板是一个两级阵列。子数组是行。每一行(数组(都有9个数字。空位置为0。共9行。例如：
[
[0,9,0,0,0,0,0,0,6],
[0,0,0,9,6,0,4,8,5],
[0,0,0,5,8,1,0,0,0],
[0,0,4,0,0,0,0,0,0],
[5,1,7,2,0,0,9,0,0],
[6,0,2,0,0,0,3,7,0],
[1,0,0,8,0,4,0,2,0],
[7,0,6,0,0,0,8,1,0],
[3,0,0,0,9,0,0,0,0]
]
孔是板上0的位置。[[row1, column1], [row2, column2] ...]，例如：
[
[0,0],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],
[1,0],[1,1],[1,2],[1,5],
[2,0],[2,1],[2,2],[2,6],[2,7],[2,8],
[3,0],[3,1],[3,3],[3,4],[3,5],[3,6],[3,7],[3,8],
[4,4],[4,5],[4,7],[4,8],
[5,1],[5,3],[5,4],[5,5],[5,8],
[6,1],[6,2],[6,4],[6,6],[6,8],
[7,1],[7,3],[7,4],[7,5],[7,8],
[8,1],[8,2],[8,3],[8,5],[8,6],[8,7],[8,8]
]
步骤(反向跟踪，像蛮力方法(：
- 遍历空位置
- 从值1开始，检查它是否有效
- 如果有效，转到下一个空位置。如果没有，请将值增加1，然后再次检查。直到值达到9
- 如果所有9个值都无效，则将当前位置值重置为0，返回到上一个空位置，将其值增加1。直到谜题解开
添加其他部件：
'use strict';
function parseBoard(board) {
return board.split('n').map(row => {
return row.split('').map(digit => {
return + digit;
});
});
}
function getEmpties(board) {
var positions = [];
for (let i = 0; i < 9; i ++) {
let array = board[i];
for (let ii = 0; ii < 9; ii ++) {
let item = array[ii];
if (item === 0) {
positions.push([i, ii]);
}
}
}
return positions;
}
function checkRow(board, row, value) {
for (let i = 0; i < 9; i ++) {
let item = board[row][i];
if (value === item) {
return false;
}
}
return true;
}
function checkColumn(board, column, value) {
for (let i = 0; i < 9; i ++) {
let item = board[i][column];
if (value === item) {
return false;
}
}
return true;
}
function checkSquare(board, row, column, value) {
var rowCorner = 0;
var columnCorner = 0;
var size = 3;
while ((row - rowCorner) >= 3) {
rowCorner += 3;
}
while ((column - columnCorner) >= 3) {
columnCorner += 3;
}
var rowEnd = rowCorner + 3;
var columnEnd = columnCorner + 3;
for (let r = rowCorner; r < rowEnd; r ++) {
let row = board[r];
for (let c = columnCorner; c < columnEnd; c ++) {
let item = row[c];
if (item === value) {
return false;
}
}
}
return true;
}
function check(board, row, column, value) {
return checkRow(board, row, value) &&
checkColumn(board, column, value) &&
checkSquare(board, row, column, value);
}
发现了问题，这是一个合乎逻辑的问题。
这就是我所做的。我控制台记录了两个功能中每一个的第一个2000板。看看有没有什么不同。差异出现在第601号板上。
运行无限的一个：
600
[ [ 8, 9, 5, 4, 2, 7, 1, 3, 6 ],
[ 2, 7, 1, 9, 6, 3, 4, 8, 5 ],
[ 4, 6, 3, 5, 8, 1, 2, 9, 7 ],
[ 9, 0, 4, 0, 0, 0, 0, 0, 0 ],
[ 5, 1, 7, 2, 0, 0, 9, 0, 0 ],
[ 6, 0, 2, 0, 0, 0, 3, 7, 0 ],
[ 1, 0, 0, 8, 0, 4, 0, 2, 0 ],
[ 7, 0, 6, 0, 0, 0, 8, 1, 0 ],
[ 3, 0, 0, 0, 9, 0, 0, 0, 0 ] ]
601
[ [ 8, 9, 5, 4, 2, 7, 1, 3, 6 ],
[ 2, 7, 1, 9, 6, 3, 4, 8, 5 ],
[ 4, 6, 3, 5, 8, 1, 2, 9, 7 ],
[ 9, 0, 4, 0, 0, 0, 0, 0, 0 ],
[ 5, 1, 7, 2, 0, 0, 9, 0, 0 ],
[ 6, 0, 2, 0, 0, 0, 3, 7, 0 ],
[ 1, 0, 0, 8, 0, 4, 0, 2, 0 ],
[ 7, 0, 6, 0, 0, 0, 8, 1, 0 ],
[ 3, 0, 0, 0, 9, 0, 0, 0, 0 ] ]
602
[ [ 8, 9, 5, 4, 2, 7, 1, 3, 6 ],
[ 2, 7, 1, 9, 6, 3, 4, 8, 5 ],
[ 4, 6, 3, 5, 8, 1, 2, 9, 7 ],
[ 9, 0, 4, 0, 0, 0, 0, 0, 0 ],
[ 5, 1, 7, 2, 0, 0, 9, 0, 0 ],
[ 6, 0, 2, 0, 0, 0, 3, 7, 0 ],
[ 1, 0, 0, 8, 0, 4, 0, 2, 0 ],
[ 7, 0, 6, 0, 0, 0, 8, 1, 0 ],
[ 3, 0, 0, 0, 9, 0, 0, 0, 0 ] ]
运行良好的一个：
600
[ [ 8, 9, 5, 4, 2, 7, 1, 3, 6 ],
[ 2, 7, 1, 9, 6, 3, 4, 8, 5 ],
[ 4, 6, 3, 5, 8, 1, 2, 9, 7 ],
[ 9, 0, 4, 0, 0, 0, 0, 0, 0 ],
[ 5, 1, 7, 2, 0, 0, 9, 0, 0 ],
[ 6, 0, 2, 0, 0, 0, 3, 7, 0 ],
[ 1, 0, 0, 8, 0, 4, 0, 2, 0 ],
[ 7, 0, 6, 0, 0, 0, 8, 1, 0 ],
[ 3, 0, 0, 0, 9, 0, 0, 0, 0 ] ]
601
[ [ 8, 9, 5, 4, 2, 7, 1, 3, 6 ],
[ 2, 7, 1, 9, 6, 3, 4, 8, 5 ],
[ 4, 6, 3, 5, 8, 1, 2, 9, 7 ],
[ 0, 0, 4, 0, 0, 0, 0, 0, 0 ],
[ 5, 1, 7, 2, 0, 0, 9, 0, 0 ],
[ 6, 0, 2, 0, 0, 0, 3, 7, 0 ],
[ 1, 0, 0, 8, 0, 4, 0, 2, 0 ],
[ 7, 0, 6, 0, 0, 0, 8, 1, 0 ],
[ 3, 0, 0, 0, 9, 0, 0, 0, 0 ] ]
602
[ [ 8, 9, 5, 4, 2, 7, 1, 3, 6 ],
[ 2, 7, 1, 9, 6, 3, 4, 8, 5 ],
[ 4, 6, 3, 5, 8, 1, 2, 9, 0 ],
[ 0, 0, 4, 0, 0, 0, 0, 0, 0 ],
[ 5, 1, 7, 2, 0, 0, 9, 0, 0 ],
[ 6, 0, 2, 0, 0, 0, 3, 7, 0 ],
[ 1, 0, 0, 8, 0, 4, 0, 2, 0 ],
[ 7, 0, 6, 0, 0, 0, 8, 1, 0 ],
[ 3, 0, 0, 0, 9, 0, 0, 0, 0 ] ]
如您所见，在第4行，第1列。当2ed列没有答案时，无穷大的一个不会将值9重置为0。然后我看一看这个循环。看起来，如果之前的空位置值是9，并将其增加1到10，它将永远不会到达while内部循环，这意味着i --或i ++无法运行，并且i < l总是无限期为真，因为i在该点是一个常数。
只需添加：
if (n === 10) {
board[row][column] = 0;
i --;
}
在内环之前，它运行良好。