寻找“8 Queens”的多种解决方案

Question

你们中的一些计算机科学、数学等专业的学生可能有遇到这个问题的经历。它被称为 8 Queens。从本质上讲，您可以用多少种不同的方式将 8 个皇后放在 8x8 的棋盘上，以使它们 none 发生冲突（也称为对角线或水平线）。我在下面尝试了这个问题，但我的程序只打印出一个解决方案。

我想我需要一个计数器。我不确定如何继续，并且没有太多的算法背景。非常感谢任何帮助，感谢您花时间提供帮助。

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

找到解决方案后，您不必 return 来自 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;
}

寻找“8 Queens”的多种解决方案

Finding Multiple Solutions to "8 Queens"

javascript

algorithm

n-queens