C++代码：N皇后问题 |21xrx.com

C++代码：N皇后问题

2023-07-09 13:27:35 深夜i -- --

C++ N皇后问题回溯算法递归棋盘布局

N皇后问题是一个经典的算法问题，其目的是在一个NxN的棋盘上放置N个皇后，使得每个皇后都不能互相攻击。对于这个问题，我们可以使用C++语言进行求解。

首先，我们需要定义一个二维数组来表示棋盘，比如使用bool型的数组board[N][N]，当board[i][j]=true时，表示第i行第j列上有一个皇后。我们需要初始化这个数组，将所有元素赋值为false。

接着，我们可以设计一个递归函数来求解N皇后问题。该函数的参数可以为当前递归到的行数，也就是我们需要在这一行放置皇后。在此之前，我们需要检查前面已经放置过的皇后是否与当前皇后互相攻击，如果攻击就无法放置，否则可以在当前行放置皇后。

当我们放置完皇后之后，需要判断是否找到了一个解，如果是，则保存当前解，否则递归调用该函数处理下一行。如果递归到最后一行还没有找到解，则回溯到上一层继续处理。

最后，在主函数中调用该递归函数，并输出所有的解。

以下是一个基于上述思路的C++代码：


#include <iostream>
using namespace std;
const int N = 10;
bool board[N][N];
void printResult() {
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      if (board[i][j]) cout << "Q ";
      else cout << ". ";
    }
    cout << endl;
  }
  cout << endl;
}
bool isAttack(int row, int col) {
  for (int i = 0; i < N; i++) {
    if (board[row][i] || board[i][col]) return true;
    int j = row - i + col;
    if (j >= 0 && j < N && board[i][j]) return true;
    j = i - row + col;
    if (j >= 0 && j < N && board[i][j]) return true;
  }
  return false;
}
void findQueen(int row) {
  if (row == N) {
    printResult();
    return;
  }
  for (int i = 0; i < N; i++) {
    if (!isAttack(row, i)) {
      board[row][i] = true;
      findQueen(row + 1);
      board[row][i] = false;
    }
  }
}
int main() {
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      board[i][j] = false;
  findQueen(0);
  return 0;
}

上面的代码在调用isAttack函数检测每个皇后是否与前面的皇后互相攻击时，使用了对角线检测的方法，可以大幅提高计算效率。

总之，N皇后问题是一个经典的算法问题，使用C++可以方便地解决该问题。在实际编程过程中，我们需要仔细审查每个细节，确保程序能够正确地求解出所有可能的解。

上一篇: idea打包java可执行jar包

下一篇: Dev C++简单密码检测程序

评论区

()

相似文章