8 皇后问题回溯算法运行时如何显示棋盘上的位置

Question

我想在回溯算法工作时重新定位板上的位置。如果我插入超时，选项卡的内存会快速增加并崩溃。我如何展示算法的功能？

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=""
    }

函数 place 和 remove 在 table 的那个位置显示皇后（并且它们工作正常）如果我删除超时，我只会看到最终的解决方案，而不会看到解决方案；

Answer 1

我认为最简单的方法是让你的函数成为一个async函数，然后使用await等待一个promise resolve（基于setTimeout）。然后您还需要 await 您的递归调用，因为该函数现在将 return 一个承诺：

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>

8 皇后问题回溯算法运行时如何显示棋盘上的位置

8-queen problem How to show the placement on a board while The backtracking algorithm is working

javascript

algorithm

performance

jsp

recursive-backtracking

8 皇后问题 回溯算法运行时如何显示棋盘上的位置

8-queen problem How to show the placement on a board while The backtracking algorithm is working

javascript

algorithm

performance

jsp

recursive-backtracking

8 皇后问题回溯算法运行时如何显示棋盘上的位置