为什么与"in order"相比，我的数独回溯求解算法中的随机顺序很慢

Question

当使用随机排序运行我的数独回溯算法来查找新的可用位置时，它比从左到右、从上到下查找可用位置花费的时间要长得多。为什么？我应该如何更改代码以进行快速随机排序？

//Taking forever
let posOrder = [[4, 4], [4, 0], [7, 0], [4, 8], [2, 3], [0, 8], [6, 0], [0, 6], [0, 5], [5, 4], [8, 2], [7, 7], [5, 1], [6, 3], [3, 2], [3, 3], [1, 2], [6, 2], [0, 7], [4, 2], [1, 4], [0, 1], [1, 1], [7, 1], [5, 2], [0, 2], [3, 7], [1, 6], [0, 4], [8, 1], [5, 6], [2, 1], [8, 3], [6, 4], [8, 6], [2, 7], [6, 6], [8, 7], [1, 8], [7, 4], [4, 7], [4, 5], [8, 4], [6, 1], [2, 2], [1, 5], [7, 6], [3, 6], [5, 0], [4, 1], [2, 8], [6, 8], [3, 1], [5, 3], [3, 4], [7, 2], [2, 5], [8, 5], [5, 5], [7, 8], [8, 8], [6, 5], [6, 7], [4, 6], [2, 6], [3, 5], [2, 0], [5, 7], [1, 0], [0, 3], [2, 4], [7, 5], [8, 0], [7, 3], [0, 0], [3, 8], [5, 8], [3, 0], [1, 7], [1, 3], [4, 3]]
//Goes quickly
//let posOrder = [[0, 0], [0, 1], [0, 2], [0, 3], [0, 4], [0, 5], [0, 6], [0, 7], [0, 8], [1, 0], [1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [2, 0], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [3, 0], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [3, 7], [3, 8], [4, 0], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [4, 7], [4, 8], [5, 0], [5, 1], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [5, 7], [5, 8], [6, 0], [6, 1], [6, 2], [6, 3], [6, 4], [6, 5], [6, 6], [6, 7], [6, 8], [7, 0], [7, 1], [7, 2], [7, 3], [7, 4], [7, 5], [7, 6], [7, 7], [7, 8], [8, 0], [8, 1], [8, 2], [8, 3], [8, 4], [8, 5], [8, 6], [8, 7], [8, 8]]
const backtrack = (board) => {
const pos = posOrder.find(p => board[p[0]][p[1]] === 0)
if(!pos)
return true
const [row, col] = pos
return (shuffleArray([1, 2, 3, 4, 5, 6, 7, 8, 9]).some(number => {
if (!numberExists(board, number, row, col)) {
board[row][col] = number
if (backtrack(board))
return true
else {
board[row][col] = 0
return false
}
}
}))
}
const shuffleArray = (array) => {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1)); // This ; is necessary... apparently
[array[i], array[j]] = [array[j], array[i]]
}
return array
}
const numberInRow = (board, number, row) => board[row].some(col => col === number)
const numberInCol = (board, number, col) => board.some(row => row[col] === number)
const numberInRegion = (board, number, row, col) => {
const r = 3*Math.floor(row/3)
const c = 3*Math.floor(col/3)
return [board[r], board[r+1], board[r+2]].some(arr=> [arr[c], arr[c+1], arr[c+2]].some(nbr => nbr === number))
}
const numberExists = (board, number, row, col) => (
numberInRow(board, number, row) ||
numberInCol(board, number, col) ||
numberInRegion(board, number, row, col)
)
const sudokuBoard = [
[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]
]
backtrack(sudokuBoard)

注意，我更喜欢每次都随机化顺序，只保留一个随机化的顺序来重新运行示例。

Answer 1

在非随机顺序中，放置9个位置后，第一行的所有重复组合都已被消除。经过27次安置，已经完成了3条线路和3个3x3盒子。这意味着必须在早期阶段考虑一些替代方案才能使其发挥作用。例如，在移动9时只有一个可能的数字。

在第一阶段，随机顺序将允许更自由地放置数字，因为许多初始坐标没有直接关系，因此在早期阶段需要重做的选择更少。这意味着更多的错误动作会在更长的时间内留在棋盘上，因此需要更多的时间才能最终被撤销并被不同的选择所取代。

为了获得更好的性能，最重要的是早期的选择是好的，不必重做。因此，这意味着必须急切地寻求数独约束。

因此，我想说，最好的顺序是尽快填写行、列和框。例如，这似乎是一个有希望的订单：

• 第一行
• 左上角的方框(因此增加了6个位置(
• 第二行(完成剩余的6个位置(
• 顶部中间框(完成剩余的3个位置(
• 第三行&右上角方框(完成剩余的3个位置(
• 第一列(完成剩余的6个位置(
• 第二列(完成剩余的6个位置(
• 。。。等等