寻找“8皇后问题”的多种解决方案

Question

你们中的一些计算机科学、数学等专业可能已经遇到过这个问题。它被广泛称为8 Queens问题。基本上，你可以在一个8x8的棋盘上放置8个皇后，使它们之间没有冲突（即在对角线或水平方向上没有重叠）。我尝试了下面的解决方案，但我的程序只打印出一个解决方案。

我想我需要一个计数器。我不确定该如何继续，并且在算法方面没有太多背景知识。非常感谢您花时间帮助，任何帮助都将不胜感激。

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

- Trevor

---

好的，找到第一个解决方案后就不要立即 return 了吗？ - Bergi

https://jsfiddle.net/zlatnaspirala/4kh6h1hg/ 我的随机访问解析！使用Canvas 2D进行可视化呈现！ - Nikola Lukic

Answer 1

当找到解决方案时，您不必从recurseNQ返回。当列等于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;
}

- StackExploded