这里我用一个类来模拟整个问题求解过程。 问题的核心部分: 怎样存储n个皇后,另一个是如何判别当前位置的皇后能否插入到棋盘中
针对这两个问题,可以采取用递归的方法解决。 首先可以用一个维位数组 ,来存储每一行皇后放置的“列数”。
另外就是要了解到使用一个判别式,来判别当前要插入的位置是否处在 已经插入的皇后的对角线上。
有了这两个基本的解决方法后,就可以使用递归来求解n皇后的排列方法,及个数。 代码如下
#include<iostream>
#include<math.h>
using namespace std;
class Queen{
int count;//皇后个数
int sloves;//解决问题的方法个数
int*p;//存储皇后保存坐标的数组 p[i]表示 第i 行的皇后放在 第p[i]列
public:
Queen(int x);//初始化参数
bool insert(int k,int i);//判断该点是否可以插入
void print();//若可以顺利按插完毕 则打印出排列
void Dqueen(int k);//递归函数遍历整个棋盘 并输出相应结果
void show();
};
Queen::Queen(int x){
count=x;
sloves=0;
p=new int[x];
}
bool Queen::insert(int k,int i){
for(int j=0;j<k;j++){
if(p[j]==i||abs(j-k)==abs(p[j]-i))//若前面的皇后 已经存放在第i列 或者和 (k,i)表示的坐标在同一对角线
return false;// abs(j-k)==abs(p[j]-i)表示前面的皇后存在和 坐标(k,i)在同一对角线的。
}
return true;
}
void Queen::print(){
for(int i=0;i<count;i++)
cout<<p[i]<<' ';
}
void Queen::Dqueen(int k){//从第1行开始遍历 所以k的值应初始化为0;
for(int i=0;i<count;i++){//检验第k行的可执行方案
if(insert(k,i)){//若能插入
p[k]=i;//则进行插入
if(k==count-1){
sloves++;//能解决则增加解决问题方法数
print();//若此时已经形成一种可行的 排列方案 则打印出
cout<<endl;
}
else Dqueen(k+1);//否则继续插入
}
}
}
void Queen::show(){
cout<<sloves;
}
void main(){
Queen a(4);
a.Dqueen(0);
a.show();
}