Suche nach mehreren Lösungen für "8 Queens"

Question

Einige von Ihnen Informatik, Mathematik, etc ... .majors könnte Erfahrung mit diesem Problem haben. Es ist bekannt als 8 Queens. Im Wesentlichen, wie viele verschiedene Möglichkeiten können Sie 8 Königinnen auf einem 8x8 Schachbrett platzieren, so dass keiner von ihnen Konflikt (aka diagonal oder horizontal). Ich habe dieses Problem unter versucht, aber mein Programm druckt nur eine einzige Lösung aus.

Ich stelle mir vor ich brauche einen Zähler. Ich bin mir nicht sicher, wie ich weitermachen soll und habe keinen großen Hintergrund in Algorithmen. Jede Hilfe wird sehr geschätzt, danke für Ihre Zeit zu helfen.

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

Sie nur müssen nicht von recurseNQ zurück, wenn Lösung gefunden. Drucken Sie die Lösung auch jedes Mal, wenn Spalte 8 entspricht. Code mit geringfügigen Änderungen unten. Der Code erzeugt 92 gültige Lösungen, die der Fall sein sollten

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; 
}