8皇后问题如何在回溯算法工作时显示板上的位置

Question

当回溯算法工作时，我想重新报告板上的位置。如果我插入一个Timeout，选项卡的ram会快速增加并崩溃。如何显示算法的功能性？

function solveNQUtil(board, col) { 
/* base case: If all queens are placed 
then return true */
if (col >= N) 
return true; 
/* Consider this column and try placing 
this queen in all rows one by one */
for (let i = 0; i < N; i++) { 
/* Check if the queen can be placed on 
board[i][col] */
place(i,col);
setTimeout(function (){
if (isSafe(board, i, col)) { 
/* Place this queen in board[i][col] */
board[i][col] = 1; 
/* recur to place rest of the queens */
if (solveNQUtil(board, col + 1) == true) {
return true; 
}
/* If placing queen in board[i][col] 
doesn't lead to a solution then 
remove queen from board[i][col] */
remove(i,col);
board[i][col] = 0; // BACKTRACK 
}
else{
remove(i,col);
}
}, 1000);
} 
/* If the queen can not be placed in any row in 
this colum col, then return false */
return false; 
}

function place(i,col){
let id="chest"+i+""+col;
document.getElementById(id).innerHTML ="&#9813;"
}
function remove(i,col){
let id="chest"+i+""+col;
document.getElementById(id).innerHTML=""
} 

功能放置和移除显示皇后在桌子上的那个位置(它们工作得很好(如果我去掉timeOut，我只看到最终解决方案，而看不到解决方案；

Answer 1

我认为最简单的方法是将函数设为async函数，然后使用await等待promise的解析(基于setTimeout(。然后还需要await递归调用，因为函数现在将返回promise：

let delay = (ms) => new Promise(resolve => setTimeout(resolve, ms));
async function solveNQUtil(table, board, col) {
if (col >= board.length) {
return true;
}
for (let i = 0; i < board.length; i++) { 
place(table, i, col);
await delay(100);
if (isSafe(board, i, col)) { 
board[i][col] = 1; 
if (await solveNQUtil(table, board, col + 1)) {
return true;
}
board[i][col] = 0;
}
remove(table, i, col);
} 
return false; 
}
function place(table, i, col){
table.rows[i].cells[col].innerHTML = "&#9813;"
}
function remove(table, i, col){
table.rows[i].cells[col].innerHTML = ""
} 
function isSafe(board, i, col) {
return !board[i].includes(1) &&
!board.some((row, j) => row[col - Math.abs(j-i)] == 1);
}
function fillHtmlTable(table, n) {
for (let row = 0; row < n; row++) {
let tr = table.insertRow();
for (let col = 0; col < n; col++) {
tr.insertCell();
}
}
return table;
}
function createBoard(length) {
return Array.from({length}, () => Array(length).fill(0));
}
// demo
let n = 8;
let table = fillHtmlTable(document.querySelector("table"), n);
solveNQUtil(table, createBoard(n), 0).then(success => {
if (success) {
table.classList.toggle("success");
} else {
console.log("NO SOLUTION");
}
});

table { border-collapse: collapse; background-color: #eee }
tr:nth-child(even) td:nth-child(odd), 
tr:nth-child(odd) td:nth-child(even) { background-color: #ccc }
td { width: 20px; height: 20px; text-align: center; font-size: 15px }
.success { color: green; font-weight: bold }

<table></table>