21xrx.com
2024-11-22 08:09:42 Friday
登录
文章检索 我的文章 写文章
N皇后问题C++代码
2023-06-28 05:31:40 深夜i     --     --
N皇后问题 C++代码 回溯算法 递归函数 棋盘网格

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


#include<iostream> 

using namespace std; 

int 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皇后问题的代码实现。这个问题的解法可以通过不断试错和优化来提高效率,在实际中也有着广泛的应用。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复