當使用隨機排序運行我的數獨回溯演算法以查找新的可用位置時，它比查找可用位置（從左到右、從上到下）花費的時間要長得多。為什么？我應該如何更改代碼以進行快速隨機排序？
//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)
請注意，我希望每次都隨機化順序，只保留一個隨機順序來重新運行示例。
uj5u.com熱心網友回復：
在非隨機順序中，在 9 次放置后，第一行可能有重復的所有組合都已被消除。在 27 次放置后，已經完成了 3 行和 3 個 3x3 框。這意味著必須在早期階段考慮一些替代方案才能使其發揮作用。例如，第 9 步只有一個可能的數字。
隨機順序將在第一階段允許更自由地放置數字，因為許多初始坐標不直接相關，因此在早期階段必須重做的選擇更少。這意味著更多的錯誤動作會在棋盤上停留更長時間，因此需要更多時間才能最終撤消并被不同的選擇取代。
為了獲得更好的性能，最重要的是早期選擇是好的并且不必重做。所以這意味著必須急切地尋求數獨約束。
因此，我會說最好的順序是盡快填充行、列和框。例如，這似乎是一個很有前途的命令：
- 第一行
- 左上角的盒子（所以用另外 6 個位置完成它）
- 第二行（完成剩余6個位置）
- 頂部中心框（完成剩余 3 個位置）
- 第三行和右上角的框（完成剩余的3個位置）
- 第一列（完成剩余6個職位）
- 第二欄（完成剩余6個職位）
- ... ETC
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/514844.html