#include <iostream>
#include <cmath>
using namespace std;
//(暂时设为100,可以通过修改N来改变规模)
# define N 100
//结果个数
int Count = 0;
//最大数组,表示"n皇后问题"的最大n,
// n<=100,目前最高支持100皇后问题
int Ar[N][N];
bool judgeUseable(int Arsize,int x,int y){ //判断(x,y)是否可插入queen
for(int i=0;i<Arsize;i++){
for(int j=0;j<Arsize;j++){
if(Ar[i][j]==1){ //找到所有的已存在的queen
if(abs(x-i) == abs(y-j) || j==y) //(斜线方向 || 竖直方向)
return false;
}
}
}
return true;
}
void printAr(int Arsize){ //打印棋盘(遍历数组)
cout<<endl;
for(int i=0;i<Arsize;i++){
for(int j=0;j<Arsize;j++){
cout << Ar[i][j] <<" ";
}
cout<<endl;
}
}
void init(int Arsize){ //初始化棋盘(将数组中所用的元素设为0) //这个函数只在主函数使用过一次.....可以直接在主函数里写......
for(int i=0;i<Arsize;i++){
for(int j=0;j<Arsize;j++){
Ar[i][j]=0;
}
}
}
void setLoc(int Arsize,int x,int y){ //安放queen //运用递归, 程序核心部分
if(x>=Arsize){ //当递归到最后一行时结束本函数
printAr(Arsize); //打印棋盘
Count++; //解个数+1
return;
}
if(y>=Arsize){ //如果列越界(本行没有任何位置可以安放queen)
return; //直接结束
}
if(judgeUseable(Arsize,x,y)){ //如果(x,y)可以安放
Ar[x][y]=1; //安放
setLoc(Arsize,x+1,0); //递归下一行
Ar[x][y]=0; //清零
setLoc(Arsize,x,y+1); //继续判断本行下一个位置是否可以安放
}
else{ //若(x,y)不可以安放
setLoc(Arsize,x,y+1); //判断(x,y+1)可不可以安放
}
}
int main() //主函数
{
int Arsize ; //这是 n 皇后问题的 n
cout << "几皇后问题? ";
cin >> Arsize;
init(Arsize); //初始化
setLoc(Arsize,0,0); //从(0,0)开始判断
cout <<"解的总数为: " << Count <<endl; //输出解
return 0;
}
/*附各n对应的解的个数
n Count
1 1
2 0
3 0
4 2
5 10
6 4
7 40
8 92
9 352
10 724
11 2680
12 14200
13 73712
14 365596
15 2279184
16 14772512
17 95815104
18 666090624
19 4968057848
20 39029188884
21 314666222712
22 2691008701644
23 24233937684440
24 227514171973736
25 2207893435808352
*/
C++回溯法解决八皇后问题(推广到n皇后)
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
