21xrx.com
2025-04-03 15:35:38 Thursday
文章检索 我的文章 写文章
N皇后问题C++代码
2023-06-28 05:31:40 深夜i     --     --
N皇后问题 C++代码 回溯算法 递归函数 棋盘网格

N皇后问题是一个著名的计算机问题,在计算机科学中,N皇后问题是试图放置N个皇后在N×N的棋盘上,使得皇后不能互相攻击到,即任意两个皇后不在同一行、同一列或者同一条对角线上。这个问题不仅在计算机科学中很有趣,而且在数学中也有广泛的应用。下面是一个基于C++的N皇后问题的代码实现。

#include<iostream> 
using namespace stdint N;//定义N 
int Chess_Queen[20];//定义棋盘数组 
bool flag;//定义结束标志 
void find(int i) 
{ 
  if (i == N)//如果已经找到一种解法 
  { 
    for (int j = 0; j < N; j++)//输出该解法 
      cout << Chess_Queen[j] + 1 << " "; 
    cout << endl; 
    flag = true;//找到了 
    return; 
  } 
  for (int j = 0; j < N; j++)//枚举列 
  { 
    bool check = true;//标记可以放置 
    Chess_Queen[i] = j;//第i行,第j列放置皇后 
    for (int m = 0; m < i; m++)//检查上面的行是否与皇后冲突 
      if (Chess_Queen[m] == j || abs(Chess_Queen[i] - Chess_Queen[m]) == i - m)//冲突 
       
        check = false; 
        break;//直接跳出循环 
       
    if (check)//如果不冲突 
      find(i + 1);//检查下一行 
    if (flag) return;//如果已经找到一种解法 
  } 
} 
int main() 
{ 
  flag = false;//标记初始化为false 
  cout << "请输入N:"; 
  cin >> N; 
  find(0);//从第0行开始查找 
  if (!flag) cout << "无解"; 
  return 0; 
}

这个代码的实现方法为:通过逐行放置皇后的方法判断是否有冲突,如果没有,则继续放置下一行的皇后,直到所有的皇后都被放置。在这个过程中,我们需要检查每一行与上面所有行的皇后是否都没有冲突,如果有冲突,就直接跳出循环进行下一次的枚举。

以上就是基于C++的N皇后问题的代码实现。这个问题的解法可以通过不断试错和优化来提高效率,在实际中也有着广泛的应用。

  
  

评论区

    相似文章