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

C++实现N皇后问题

2023-07-07 16:57:14 深夜i -- --

C++ N皇后问题回溯算法递归数组

N皇后问题是一种经典的考验算法能力的问题，其要求在N*N的棋盘上摆放N个皇后，要求任意两个皇后不在同一行、同一列和同一斜线上。本文将介绍如何使用C++语言实现解决N皇后问题。

首先，我们需要定义皇后的位置，一般使用一维数组来表示，数组下标表示皇后所在的行，数组的值表示皇后所在的列。比如，下标为0的值为2，表示第0行的皇后在第2列。

接下来，我们需要实现一个验证函数，用于检测皇后位置是否合法。在验证函数中，我们需要遍历当前皇后的位置与之前的皇后位置，判断是否在同一列或同一斜线上。如果存在冲突，就返回false，否则返回true。

然后，我们需要实现一个回溯函数，用于尝试将皇后放置在棋盘上。在回溯函数中，我们需要遍历每一行，对于每一行我们需要遍历每一列，尝试将皇后放置在该位置，然后调用验证函数检测该位置是否合法，如果合法，就继续递归下一行皇后的位置，如果不合法，就需要回溯到上一个位置重新尝试。

最后，我们需要实现一个主函数，用于调用回溯函数并输出结果。在主函数中，我们需要定义一个棋盘数组，用于保存每个皇后的位置，然后调用回溯函数，并输出结果。

下面是一段示例代码，演示如何使用C++实现N皇后问题。

#include <iostream>
#include <vector>
using namespace std;
bool isValid(vector<int>& board, int row, int col) {
  for (int i = 0; i < row; ++i) {
    if (board[i] == col || abs(board[i] - col) == abs(i - row))
      return false;
    
  }
  return true;
}
void backtrack(vector<vector<int>>& res, vector<int>& board, int row) {
  int n = board.size();
  if (row == n) {
    res.push_back(board);
    return;
  }
  for (int col = 0; col < n; ++col) {
    if (!isValid(board, row, col)) continue;
    board[row] = col;
    backtrack(res, board, row + 1);
    board[row] = -1;
  }
}
vector<vector<int>> solveNQueens(int n) {
  vector<vector<int>> res;
  vector<int> board(n, -1);
  backtrack(res, board, 0);
  return res;
}
int main() {
  int n = 4;
  vector<vector<int>> res = solveNQueens(n);
  for (auto& r : res) {
    for (auto& e : r)
      cout << e << " ";
    
    cout << endl;
  }
  return 0;
}

通过上述代码，我们就可以解决N皇后问题了。当然，为了进一步提高效率，我们可以对上述代码进行一些优化，例如：剪枝、使用位运算等。这些优化将在以后的文章中介绍。

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

下一篇: C++中链表：数据结构与实现

评论区

相似文章