算法 dfs 八皇后问题详解（深度优先搜索）C++

八皇后问题详解（dfs深度优先搜索）C++

八皇后问题概念思路讲解代码步骤讲解完整代码

八皇后问题概念

八皇后问题是由国际象棋棋手马克斯·贝瑟尔于1848年提出的问题。

问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一或同一斜线上，问有多少种摆法?

思路讲解

条件：每一行、每一列、主副对角线上只能有一个皇后。 而且一定是有解的。 思路不难。肯定的是，最终每行只有一个皇后，那么可以以行数为大基准逐行搜索，对第n行0搜索时，依次对每一列进行搜索，一旦找到满足条件的位置，就跳到下一行继续搜索，如果一行中的8列都不能满足条件就返回上一行，继续搜索，直到找到满足条件的一条路径（一种摆法）。然后跳出这条路径，到第一行下一个符合的元素继续搜索。

代码步骤讲解

1

#include

using namespace std;

int ans=0;//总摆法数

bool col[10],v1[20],v2[20];//标记该列、主对角线、右对角线，均无其他皇后为false(全局布尔变量初始为false)

这里用ans记录摆法的总数（题目要求的答案）。然后定义三个布尔数组，col记录列是否满足条件，v1记录主对角线是否满足条件，v2记录副对角线是否满足条件，如果满足（即可以放皇后）为false,不满足为true。 注 1.定义全局变量是因为这些变量的生存期一直到程序结束，并且一直不需要初始化，因此变量不会因为出了函数作用域而改变（避免了一些指针的操作）。使程序更简洁。  2. 列是8，于是定义10个元素的数组；（算上顶点）主副对角线各有17个，于是两个数组定义元素20个。 2

int main(){

dfs(0);//从第0行开始找

cout<

return 0;

}

先把主函数写好，这样更能看清深搜函数（dfs）的作用。这题没有输入，直接从第0行开始深度搜索（后面详细会讲），dfs内会计算ans（摆法总数)，最后在主函数中输出。 3

void dfs(int r){

//如果超出最大行数，则该路径结束，继续找下一个路径

if(r==8){

ans++;//总方法数+1

return;

}

if这里是递归终止的条件。参数r代表行数。进入dfs后首先判断行数有没有超过8（由于存放在数组中，0代表1，7代表8），如果已经到了第九行，说明前8行已经搜索完了，找到了一种摆法（否则第八行找不到的话，就会返回第7行，因而到不了第9行）。所以结束当前路径dfs，进入除去已找到摆法中第一行的元素的下一列。 4

for(int i=0;i<8;i++){

//如果此位置所在列、主对角线、右对角线均无其他皇后,则放置一个皇后

if(!col[i]&&!v1[r+i]&&!v2[r-i+8]){

col[i]=v1[r+i]=v2[r-i+8]=true;//先标记为true,即此位置所在列、主副对角线已不能放其他皇后

dfs(r+1);// 接着去下一行搜索符合放置皇后条件的位置

col[i]=v1[r+i]=v2[r-i+8]=false;//如果路径行不通，返回上一级，标记为true,相当于该位置未走过

}

}

}

这里开始深搜，从当前行r开始往后找每一列，一旦找到符合条件的位置就放一个皇后(标记为true)。然后dfs(r+1)进入下一行继续每行找。最后一句是如果在这一行搜索不到符合条件的位置就返回上一行并把上一行此路径中标记为true的元素改为false(此时上一行该位置可以放皇后但如果放了，在这一行是搜索不到符合条件的位置，所以上一行该位置不能放)，接着继续在上一行原位置的下一列进行搜索。

数组下标：这里i表示第i行。对于对角线的表示，因为我们是从左上角开始搜索的（或者把棋盘看成一个二维数组，起始点自左上角），那么如果将棋盘类比成平面直角坐标系，左上角的点就是坐标原点O。可以把i看作横坐标，r看作纵坐标，若主对角线v1是不通过O的，那么v1上的点的横纵坐标之和不变，即r+i不变，副对角线v2上的点的横纵坐标只差不变即r-i不变，但是r-i会小于0（最小为0-8==-8），由于数组下标的限制，所以要对r-i加8。(如下图)

完整代码

#include

using namespace std;

int ans=0;//总方法数

bool col[10],v1[20],v2[20];//默认都是false(该列、主对角线、右对角线均无其他皇后)

void dfs(int r){

//如果超出最大行数，则该路径结束，继续找下一个路径

if(r==8){

ans++;//总方法数+1

return;

}

for(int i=0;i<8;i++){

//如果此位置所在列、主对角线、右对角线均无其他皇后,则放置一个皇后

if(!col[i]&&!v1[r+i]&&!v2[r-i+8]){

col[i]=v1[r+i]=v2[r-i+8]=true;//先标记为true,即此位置所在列、主副对角线已不能放其他皇后

dfs(r+1);// 接着去下一行搜索符合放置皇后条件的位置

col[i]=v1[r+i]=v2[r-i+8]=false;//如果路径行不通，返回上一级，标记为true,相当于该位置未走过

}

}

}

int main(){

dfs(0);//从第0行开始找

cout<<"总共有"<

return 0;

}

解决！ 本人拙见，请读者多加指教。

精彩链接