Поиск нескольких решений для «8 Queens»

Question

Некоторые из вас - компьютерные науки, математика и т. Д.. Майоры могут иметь опыт работы с этой проблемой. Он известен как 8 Queens. По сути, сколько разных способов вы можете разместить 8 королев на шахматной доске 8x8, чтобы ни один из них не конфликтует (ака по диагонали или по горизонтали). Я попытался решить эту проблему ниже, , но моя программа выводит только одно решение.

Полагаю, мне нужен счетчик. Я не уверен, как продолжить, и не имею большого фона в алгоритмах. Любая помощь очень ценится, спасибо, что потратили свое время на помощь.

var n = 8; 

solveNQ(); 

function printSolution(board){ 
    for(var i=0; i<n; i++){ 
    for(var j=0; j<n; j++){ 
     document.write(" "+board[i][j]+" "); 
    } 
    document.write("<br>"); 
    } 
    document.write("<br>"); 
} 

function isSafe(board, row, col){ 

    // Checks the ← direction 
    for(var i=0; i<col; i++){ 
    if (board[row][i] === 1) { 
     return false; 
    } 
    } 

    // Checks the ↖ direction 
    for(var i=row, j=col; i>=0 && j>=0; i--, j--){ 
    if (board[i][j] === 1) { 
     return false; 
    } 
    } 

    // Checks the ↙ direction 
    for(var i=row, j=col; j>=0 && i<n; i++, j--){ 
    if (board[i][j] === 1){ 
     return false; 
    } 
    } 

    return true; 
} 


function recurseNQ(board, col){ 
    if(col>=n){ 
    return true; 
    } 

    for(var i=0; i<n; i++){ 
    if(isSafe(board, i, col)){ 
     board[i][col]=1; 

     if(recurseNQ(board, col+1)===true) 
     return true; 

     board[i][col]=0; 
    } 
    } 
    return false; 
} 


function solveNQ(){ 
    var board = generateBoard(n); 
    if(recurseNQ(board, 0)===false){ 
    console.log("No solution found"); 
    return false; 
    } 
    printSolution(board); 
} 

function generateBoard(n){ 
    var board=[]; 
    for(var i=0; i<n; i++){ 
    board[i]=[]; 
    for(var j=0; j<n; j++){ 
     board[i][j]=0; 
    } 
    } 
    return board; 
} 

Answer 1

Вам просто не нужно возвращаться из recurseNQ, когда решение найдено. Также печатайте решение каждый раз, когда col равно 8. Код с небольшими изменениями ниже. Код создает 92 действительных решения, которые должны быть в таком случае

var n = 8; 

solveNQ(); 

function printSolution(board){ 
    for(var i=0; i<n; i++){ 
    for(var j=0; j<n; j++){ 
     document.write(" "+board[i][j]+" "); 
    } 
    document.write("<br>"); 
    } 
    document.write("<br>"); 
} 

function isSafe(board, row, col){ 

    // Checks the ← direction 
    for(var i=0; i<col; i++){ 
    if (board[row][i] === 1) { 
     return false; 
    } 
    } 

    // Checks the ↖ direction 
    for(var i=row, j=col; i>=0 && j>=0; i--, j--){ 
    if (board[i][j] === 1) { 
     return false; 
    } 
    } 

    // Checks the ↙ direction 
    for(var i=row, j=col; j>=0 && i<n; i++, j--){ 
    if (board[i][j] === 1){ 
     return false; 
    } 
    } 

    return true; 
} 


function recurseNQ(board, col){ 
    if(col===n){ 
     printSolution(board); // <-- print another solution when n==8 
    return; 
    } 

    for(var i=0; i<n; i++){ 
    if(isSafe(board, i, col)){ 
     board[i][col]=1; 

     recurseNQ(board, col+1); 
     //if(recurseNQ(board, col+1)===true) //<-- you don't need this 
      // return true; 

     board[i][col]=0; 
    } 
    } 
    return false; 
} 


function solveNQ(){ 
    var board = generateBoard(n); 
    recurseNQ(board, 0); 
    //if(recurseNQ(board, 0)===false){ 
    //console.log("No solution found"); 
    // return false; 
// } 
// printSolution(board); 
} 

function generateBoard(n){ 
    var board=[]; 
    for(var i=0; i<n; i++){ 
    board[i]=[]; 
    for(var j=0; j<n; j++){ 
     board[i][j]=0; 
    } 
    } 
    return board; 
}