C++实现n皇后问题求解并输出所有解法 |21xrx.com

C++实现n皇后问题求解并输出所有解法

2023-07-09 17:07:05 深夜i -- --

C++ n皇后问题求解输出解法

在计算机编程领域中，n皇后问题是一个经典的问题。这个问题的目标是找到如何将n个皇后放置在n x n的棋盘上，使得它们不会互相攻击，也就是说，在同一行、同一列或同一对角线上不会有两个皇后。

这个问题可以通过使用C ++编程语言来解决。在C ++中，可以使用递归算法来找到所有可能的解法并输出。

首先，我们需要定义一个函数来检查位置是否合法。这个函数会检查一个新的皇后是否会与之前已放置皇后产生冲突。在这个函数中，可以使用一个二维数组来表示棋盘，并在其中将已放置皇后的位置进行标记。

接下来，我们可以编写一个递归函数来依次放置皇后。在这个函数中，我们首先需要检查所有列，以查找当前行中可以放置的正确位置。然后，我们将一个皇后放置在当前列，标记棋盘上对应的位置，并递归调用同样的函数来放置下一个皇后。

这个递归函数会基于当前状态继续向下搜索，直到找到所有解。当所有皇后都被放置在棋盘上时，我们会在屏幕上打印输出所有解法。

最后，我们需要编写一个主函数来初始化棋盘、调用递归函数并输出所有解法。

下面是一份示例代码，用于解决n皇后问题并输出所有解法。


#include <iostream>
using namespace std;
const int MAX_N = 10;
bool board[MAX_N][MAX_N];
int n;
// 检查新皇后是否可以放置
bool is_valid(int row, int col) {
  int i, j;
  for(i=0;i<col;i++) // 检查当前列之前的每一列
    if(board[row][i]) // 是否有皇后
      return false;
  for(i=row,j=col; i>=0 && j>=0; i--,j--) // 检查左上方
    if(board[i][j]) // 是否有皇后
      return false;
  for(i=row,j=col; j>=0 && i<n; i++,j--) // 检查左下方
    if(board[i][j]) // 是否有皇后
      return false;
  return true;
}
// 递归地放置皇后
bool solve(int col) {
  if(col>=n) { // 所有皇后都被放置到棋盘上
    for(int i=0; i<n; i++) {
      for(int j=0; j<n; j++)
        cout<<board[i][j]<<" ";
      cout<<endl;
    }
    cout<<endl;
    return true;
  }
  bool res = false;
  for(int i=0; i<n; i++) { // 逐行放置皇后
    if(is_valid(i, col)) {
      board[i][col] = true;
      res |= solve(col+1);
      board[i][col] = false;
    }
  }
  return res;
}
int main() {
  cout<<"Input the number n: ";
  cin>>n;
  // 初始化棋盘
  for(int i=0; i<n; i++)
    for(int j=0; j<n; j++)
      board[i][j] = false;
  // 解决问题并输出结果
  solve(0);
  
  return 0;
}

当运行此程序时，用户将首先被要求输入n值（皇后数），然后程序会自动解决问题并打印输出所有解法。对于较小的n，有时结果可以在几秒钟内计算出。但是，对于较大的n，这个问题变得非常复杂，需要处理大量的情况和冲突。

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

下一篇: C++第二版课后习题答案

评论区

()

相似文章