c++递归实现n皇后问题代码(八皇后问题)
5星 · 超过95%的资源 184 浏览量
2020-12-31
22:28:03
上传
评论
收藏 58KB PDF 举报 
c++递归实现递归实现n皇后问题代码皇后问题代码(八皇后问题八皇后问题)
还是先来看看最基础的8皇后问题：
在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多
少种摆法。
扩展到N皇后问题是一样的。
一看，似乎要用到二维数组。其实不需要。一维数组就能判断，比如Arr[i]，就可以表示一个元素位于第i行第Arr[i]列——应用
广泛的小技巧。而且在这里我们不用考虑去存储整个矩阵，如果Arr[i]存在，那么我们在打印的时候，打印到皇后位置的时候
输出1，非皇后位输出0即可。
这种思路的实现方式网上大把，包括前面提到的那位同学，所以也就不要纠结有没有改善有没有提高之类的了，权当一次练习
即可。
直接上代码好了，觉得递归方法没什么好说的，空间想想能力好一点儿很容易理解。明天有空再写写非递归实现吧。
代码如下:
/*
* NQueen.cpp
*
* Created on: 2013年12月23日
* Author: nerohwang
*/
//形参rowCurrent表示当前所到的行数
#include<iostream>
#include<fstream>
#include<iomanip>
#include<stdlib.h>
using namespace std;
bool Check(int rowCurrent,int *&NQueen); //判断函数
void Print(ofstream &os,int n,int *&NQueen); //打印函数
void Solve(int rowCurrent,int *&NQueen,int n,int &count, ofstream &os); //N皇后问题处理函数，index一般初值为0
//判断函数，凡是横竖有冲突，或是斜线上有冲突，返回FALSE
bool Check(int rowCurrent,int *&NQueen)
{
int i = 0;
while(i < rowCurrent)
{
if(NQueen[i] == NQueen[rowCurrent] || (abs(NQueen[i]-NQueen[rowCurrent]) == abs(i-rowCurrent)) )
{
return false;
}
i++;
}
return true;
}
//将所有可能出现的结果输出文本文档
void Print(ofstream &os,int n,int *&NQueen)
{
os<<“一次调用”;
for (int i = 0;i < n;i++) {
for(int j = 0 ; j < n; j++)
评论10
最新资源