八皇后问题 c++递归实现n皇后问题代码(八皇后问题)
人气:0还是先来看看最基础的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<<"一次调用\n";
for (int i = 0;i < n;i++) {
for(int j = 0 ; j < n; j++)
{
os<<(NQueen[i]==j?1:0);
os<<setw(2);
}
os<<"\n";
}
os<<"\n";
}
//核心函数。递归解决N皇后问题，触底则进行打印
void Solve(int rowCurrent,int *&NQueen,int n,int &count, ofstream &os)
{
if(rowCurrent == n) //当前行数触底，即完成了一个矩阵，将它输出
{
Print(os,n,NQueen);
count++;
}
for(int i = 0; i < n; i++)
{
NQueen[rowCurrent] = i; //row行i列试一试
if(Check(rowCurrent,NQueen))
{
Solve(rowCurrent+1,NQueen,n,count,os); //移向下一行
}
}
}
int main()
{
int n; //问题规模
int count = 0; //解的计数
cout<<"请输入问题的规模N"<<endl;
cin>>n;
if(n<4)
{
cerr<<"问题规模必须大于4"<<endl;
return 0;
}
int *NQueen = new int[n];
ofstream os;
os.open("result.txt");
Solve(0,NQueen,n,count,os);
cout<<"问题的解有"<<count<<"种方法"<<endl;
os.close();
return 0;
}
加载全部内容