详解以后慢慢补,看心情。。。
#include<iostream>
#include<cstring>
using namespace std;
int vis[3][8*8];//vis[0][]表示同一列,vis[1][]和vis[2][]表示两个对角线;
int tot;
void search(int cur)
{
if(cur==8) tot++;
for(int i=0;i<8;i++)
{
if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+8])
{
vis[0][i]=vis[1][cur+i]=vis[2][cur-i+8]=1;
search(cur+1);
vis[0][i]=vis[1][cur+i]=vis[2][cur-i+8]=0;
}
}
}
int main()
{
tot=0;
memset(vis,0,sizeof(vis));
search(0);
cout<<tot<<endl;
return 0;
}
下面这个是有注释的,慢慢列举理解吧~~
之前不知道看到哪位博主的,我觉得很可以
//在8*8的棋盘上放n个皇后,返回解法种类的数目
//枚举法(2的64次幂次)和组合生成法(40320次)严重超时,需要一种新的方法
#include<iostream>
#include<cstring>
#include<string>
#define N 8 //8*8棋盘
using namespace std;
int tot,n,vis[3][N*N];
//vis的0,1,2分别用来储存和调用列,主对角线,副对角线的情况
//要求返回解的数目,则定义全局变量tot作为返回值
//解体的关键在于:
//确定一个皇后的位置可行以后,
//将她能辐射到的区域都标记下来
//并递归到下一个皇后
//如果下一个皇后的位置不幸被前几位皇后污染(区域已被标记为1),
//就需要“退回去”,将此皇后的标记清零,并寻找下一个可行的位置,
//也就是“回溯”
void search(int cur){
if(cur==n) tot++;
else for(int i=0;i<N;i++){
//将第一个皇后确定在0行,然后改变她的列数i以确定其他皇后的位置
//依此类推,一个萝卜一个坑,一个皇后站一行,每确定一个就cur++一次。
//当cur==n,即八个皇后都已被安置
//则已确认一个可行解,tot++记录下来
//因此,不会出现行的横向攻击,因此i可以表示一整列
//另外由于副对角线y+x=i;
//主对角线y-x=i(但会出现y-x<0的情况,使用时需要加N)
//因此可以用i同时表示列,主、副对角线的情况
if(!vis[0][i]&&!vis[1][cur+i]&&!vis[2][cur-i+N]){
//如果这里目前没有被前面的皇后占有
vis[0][i]=vis[1][cur+i]=vis[2][cur-i+N]=1;
//则由这位皇后污染这片区域(标记为1)
search(cur+1);
//并递归下一位皇后
vis[0][i]=vis[1][cur+i]=vis[2][cur-i+N]=0;
//最重要的一步 ! ! ! ! ! !
//既是给错误解留条后路,也为继续搜寻正确解留条活路
//(事实上这两步的区别就在于是否“tot++”)
//总之,“改回来”这一步一定要有!!!!!
}
}
}
int main(void){
cin>>n;//输入需要安置的皇后数n
tot=0;//将tot清零
memset(vis,0,sizeof(vis));
//将标记数组vis清零
search(0);//调用函数得到解的个数tot
cout<<tot<<endl;//输出
return 0;
}