C++实现N皇后问题 |21xrx.com

C++实现N皇后问题

2023-07-01 12:58:13 深夜i -- --

C++ N皇后问题实现

N皇后问题是指在一个N*N的棋盘上放置N个皇后，使得它们互相不能攻击，即任意两个皇后不能在同一行、同一列或同一斜线上。这是一个经典的递归与回溯问题。

为了解决N皇后问题，我们可以使用C++语言进行编程实现。以下是一些关键的步骤和方法。

首先，我们需要定义一个二维数组来表示棋盘，并初始化为0。接下来，我们定义一个函数check，用于检查当前行和列是否合法。该函数接受当前行号和列号作为参数，并返回一个布尔值。如果当前行和列不合法，则返回false；否则返回true。

其次，我们需要定义一个递归函数来解决N皇后问题。该函数接受一个整数n作为参数，并返回一个布尔值。如果可以在当前位置放置皇后，则继续尝试下一行；如果无法放置，则回溯回来重新尝试。

在该递归函数中，我们首先需要遍历当前行的每一列。如果当前位置可以放置皇后，则将该位置标记为1，并尝试下一行。否则，继续尝试下一列。

如果当前位置无法放置皇后，则回溯回来重新尝试。为实现回溯操作，我们需要在该位置将之前放置的皇后标记取消，并继续尝试下一列。直到所有列都尝试完毕，该递归函数才会返回false。

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

下面是N皇后问题的完整C++实现代码。


#include<iostream>
#include<cmath>
using namespace std;
const int MAXN = 100;
int n, cnt, a[MAXN][MAXN];
bool check(int row, int col) {
  for (int i = 0; i < row; i++) {
    if (a[i][col]) return false;
    if (col-row+i >= 0 && a[i][col-row+i]) return false;
    if (col+row-i < n && a[i][col+row-i]) return false;
  }
  return true;
}
void solve(int row) {
  if (row == n) {
    cnt++;
    return;
  }
  for (int i = 0; i < n; i++) {
    if (check(row, i)) {
      a[row][i] = 1;
      solve(row+1);
      a[row][i] = 0;
    }
  }
}
int main() {
  cin >> n;
  solve(0);
  cout << cnt << endl;
  return 0;
}

在该代码中，我们使用check函数来检查当前位置是否可以放置皇后，并在主函数中使用solve递归函数来解决N皇后问题。最后，我们输出所有解的数量。

总之，C++是一种非常有用的编程语言，可以帮助我们轻松地实现各种算法和问题的求解。在解决N皇后问题时，我们只需遵循上述步骤和方法，即可成功实现该问题的求解。

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

下一篇: 使用devc++制作一个心形图案

评论区

()

相似文章