Проблема с 8 ферзями Как показать размещение на доске при работе алгоритма отката - PullRequest
Новая
       20

Проблема с 8 ферзями Как показать размещение на доске при работе алгоритма отката

1 голос
/ 08 мая 2020

Я хочу воспроизвести размещение на доске, пока работает алгоритм обратного отслеживания. Если я вставляю тайм-аут, барабан вкладки быстро увеличивается и вылетает. Как я могу показать функциональность алгоритма? 

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 and remove показывает ферзей на столе в этой позиции (И они работают нормально) Если я удалю timeOut, я вижу только окончательное решение но не разрешение;

1 Ответ

2 голосов
/ 08 мая 2020

Я думаю, что проще всего сделать вашу функцию функцией async, а затем использовать await для ожидания разрешения обещания (на основе setTimeout). Затем вам также потребуется await ваши рекурсивные вызовы, поскольку функция теперь будет возвращать обещание: 

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>
...