算法设计:回溯法-n皇后问题 n皇后问题java回溯法解析

N皇后问题

一、问题描述

在N X N的棋盘放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之在同一行、同一列、同一斜线上的棋子。设计算法在N X N 的棋盘上放置n个皇后，使其彼此不受攻击

二、问题分析

棋盘如图所示，我们在第i行第j列放置一个皇后，那么第i行的其它位置（同行），那么第j列的其它位置（同列），同一斜线上的其它位置，都不能放置皇后

条件是这样要求的，但是我们不可能杂乱无章的尝试每个位置，要有求解策略。我们可以以行为主导：

（1）在第1行第1列放置第1个皇后

（2）在第2行放置第2个皇后。第2个皇后的位置不能和第1个皇后同列、同斜线，不用再判断是否同行了

（3）在第3行放置第3个皇后，第3个皇后的位置不能和前2个皇后同列、同斜线

（4）在第t行放置第t个皇后，第t个皇后的位置不能和前t-1个皇后同列、同斜线

（5）在第n行放置第n个皇后，第n个皇后的位置不能和前n-1个皇后同列、同斜线

三、算法设计

1、定义解空间

N皇后问题的解形式为n元组：{x1 , x2,x3,…..,xi,…..xn}，分量xi表示第i个皇后放置在第i行第xi列，xi的取值为1,2,3,….,n。例如：x2 = 5表示第2个皇后放置在第2行第5列。显约束为不同行

2、解空间的组织结构

N皇后解空间是一个m(m = n)叉树，数的深度为n

3、搜索解空间

（1）约束条件

在第t行放置第t个皇后时，第t个皇后的位置不能和前t-1个皇后同列、同斜线。第i个皇后和第j个皇后不同列，即xi ! = xj，并且不同斜线，即 | i – j | ! = | xi – xj |

（2）限界条件

该问题不存在放置方案好坏情况，所以不需要设置限界条件

（3）搜索过程

从根开始，以深度优先搜索的方式进行搜索。根节点是活节点，并且是当前的扩展节点。在搜索过程中，当前的扩展节点沿着纵深方向移向一个新节点，判断该节点是否满足隐约束。如果满足，则新节点成为活节点，并且称为当前的扩展节点，继续深一层的搜索；如果不满足，则换到该新节点的兄弟节点继续搜索；如果新节点没有兄弟节点，或其兄弟节点已经全部搜索完毕，则扩展节点称为死节点，搜索回溯到其父节点处继续进行。搜索过程直到找到问题的根节点变成死节点为止

4、算法图解

为了说明问题，我们在4x4的棋盘上放置4个皇后，使其彼此不受攻击

（1） 开始搜索第1层（t = 1）

扩展1号节点，首先判断x1 = 1是否满足约束条件，因为之前还未选中任何节点，满足约束条件。令 x[1] = 1 ，生成2号节点

（2）扩展2号节点（t = 2）

首先判断x2=1不满足约束条件，因为和之前放置的第1个皇后同列；考查x2 = 2也不满足约束条件，因为和之前放置的第1个皇后同斜线；考查x2 =3满足约束条件，和之前放置的皇后不同列、不同斜线，令x[2] = 3，生成3号节点

（3）扩展3号节点

首先判断x3=1不满足约束条件，因为和之前放置的第1个皇后同列；考查x2 = 2也不满足约束条件，因为和之前放置的第2个皇后同斜线；考查x3 =3不满足约束条件，因为和之前放置的第2个皇后同列；考查x3=4也不满足条件，因为和之前放置的第2个皇后同斜线；3号节点所有的孩子都已经考查完毕，3号节点成为死节点，向上回溯到2号节点

（4）重新扩展2号节点（ t = 2）

判断x = 4满足约束条件，因为和之前放置的第1个皇后不同列、不同斜线，领x[2] = 4,生产4号节点，如图：

（5）扩展4号节点 （ t =3 ）

首先判断x3=1不满足条件，因为之前放置的第1个皇后同列；考查x3=2满足约束条件，因为和之前放置的第1、2个皇后不同列、不同斜线令x[3]=2，生成5号节点，如图：

（6）扩展5号节点（ t =4 ）

首先判断x4=1不满足约束条件，因为和之前放置的第1个皇后同列；考查x4=2也不满足约束条件，因为和之前放置的第3个皇后同列；考查x4=3不满足约束条件，因为和之前放置的第3个皇后同斜线；考查x4=4也不满足约束条件，因为和之前放置的第2个皇后同列；5号节点所有孩子均已考查完毕，5号节点成为死节点，向上回溯到4号节点

（7）继续扩展4号节点（ t = 3）

判断x3=3不满足约束条件，因为和之前放置的第2个皇后同斜线；考查x3=4也不满足约束条件，因为和之前放置的第2个皇后同列。4号节点所有孩子均已考查完毕，4号节点成为死节点。向上回溯到2号节点，2号节点所有孩子节点均已经考查完毕，2号节点成为死节点，向上回溯到1号节点

（8）继续扩展1号节点（t=1）

判断x1=2是否满足约束条件，因为之前还未选中任何节点，满足约束条件。令x[1]=2，生成6号节点，如图：

（9）扩展6号节点（t=2）

判断x2=1不满足约束条件，因为和之前放置的第1个皇后同斜线；考查x2=2也不满足约束条件，因为和之前放置的第1个皇后同列；考查x2=3不满足约束条件，因为和之前放置的第1个皇后同斜线；考查x2=4满足约束条件，令x[2] = 4，生成7号节点

（10）扩展7号节点（t=3）

判断x3=1满足约束条件，因为和之前放置的第1、2个皇后不同列、不同斜线，令x[3]=1，生成8号节点，如图：

（11）扩展8号节点（t=4）

判断x4=1不满足约束条件，因为和之前放置的第3个皇后同列。

。。。

考查x4=3满足约束条件，令x[4] = 3生成9号节点，如图：

（12）扩展9号节点（t=5）

t > n找到一个可行解。用bestx[]保存当前可行解{2,4,1,3} 。9号节点成为死节点，向上回溯到8号节点

（13）继续扩展8号节点（t=4）

判断x=4不满足约束条件。至此8号节点考查完毕，成为死节点。向上回溯到7号节点

（14）继续扩展7号节点（t=3）

判断x3=2不满足;x3=3不满足；x3=4不满足。所有节点考查完毕，7号节点为死节点。向上回溯到6号节点，6号节点所有孩子考查完毕，成为死结点，向上回溯到1号节点，如图：

（15）继续扩展1号节点（t=1）

判断x1=3满足约束条件，令x[1]=3生成10号节点

（16）扩展10号节点（t=2）

首先判断x2=1满足约束条件；令x[2] =1生成11号节点

（17）扩展11号节点

判断x3=1不满足；x3=2不满足；x3=3不满足。X3=4满足条件，令x[3]=4，生成12号节点，如图：

（18）扩展12号节点（t=4）

判断x4=1不满足约束条件；x4=2满足约束，令x[4]=2，生成13号节点

（19）扩展13号节点（t=5）

t>n，找到一个可行解，用bestx[]保存当前可行解{3,1,4,2}。13号节点为死节点，向上回溯到12号节点

（20）继续扩展12号节点（t=4）

判断x4=3不满足；x4=4不满足；12号节点为死节点。向上回溯到11号节点。11号节点所有孩子均已经考查，成为死节点。再向上回溯到10号节点

（21）继续扩展10号节点（t=2）

判断x2=2不满足；判断x2=3不满足；判断x2=4不满足；10号节点为死节点。向上回溯到1号节点

（

（22）继续扩展1号节点（t=1）

判断x1=4是否满足，因为之前无任何节点，所以满足。令x[1]=4，生成14号节点，如图：

（23）扩展14号节点（t=2）

首先判断x2=1满足约束条件，令x[2]=1，生成15号节点，如图：

（24）扩展15号节点（t=3）

判断x3=1不满足；x3=2不满足；x3=3满足条件。令x[3]=3，生成16号节点，如图：

（25）扩展16号节点（t=4）

首先判断x4=1不满足；x4=2不满足；x4=3不满足；x4=4不满足,16号节点为死节点，向上回溯到15号节点

（26）继续扩展15号节点（t=3）

判断x3=4不满足约束条件；15号考查完毕为死节点；向上回溯到14号节点

（27）继续扩展14号节点（t=2）

判断x2=2满足，令x[2]=2，生成17号节点：

（28）扩展17号节点（t=3）

判断x3=1不满足；x3=2不满足；x3=3不满足；x3=4不满足。17号考查完毕，成为死节点，向上回溯到14号节点

（29）继续扩展14号节点（t=2）

判断x2=3不满足；x2=4不满足。14号考查完毕，回溯到1号节点

（30）1号所有均已经考查完毕，都是死节点。算法结束，如图：

5、伪代码详解

（1）约束函数

在第t行放置第t个皇后的时候，第t个皇后与前t-1个已经放置好的皇后不能再同一列或者同一斜线，如果有一个成立，则第t个皇后不可以放置在该位置

X[t] == x[j] 表示第t个皇后和第j个皇后位置在同一列，t-j==fabs(x[t]-x[j])表示第t个皇后和第j个皇后位置在同一斜线。fabs是求绝对值，使用该函数要引入头文件#include<cmath>

//判断第t个皇后是否能放在第i个位置

bool place(int t)

{

bool ok = true;

//判断该位置的皇后是否与前面t-1个已经放置好的皇后冲突

for( int j = 1 ; j < t ; j ++)

{

//判断同列、对角线是否冲突

if (x[t] == x[j] || t – j == fabs( x[t] – x[j] ) )

{

ok = false;

break;

}

}

return ok;

}

（2）按照约束条件搜索求解

t表示当前扩展节点在第t层。如果r > n，表示已经到达叶子节点，记录最优值和最优解，返回。否则，分别判断 n （i = 1,….,n）个分支，x[t] =i ；判断每个分支是否满足约束条件，如果满足则进入下一层backTrack(t+1)；如果不满足则考查下一个分支（兄弟节点）

void backTrack(int t)

{

//如果当前位置为n，则表示已经找到问题的一个解

If( t > n)

{

Count + +;

//打印选择的路径

For(int I = 1; i<=n ;i++)

{

Cout<<x[i]<<"";

Cout<<endl;

Cout<<"---------------------"<<endl;

}

}else{

//分别判断n个分支，特别注意i不要定义为全局变量，否则递归调用有问题

For(int I = 1; i<=n ; i++){

x[t] = i;

//如果不冲突的话进行下一行搜索

If( place(t) ){

backTrack(t+1);

}

}

}

}

6、代码实现：

#include <iostream>

#include <cmath>

#define M 105

using namespace std;

int n=4;//4个皇后

int x[M];//x[i]表示第i个皇后放在第i行第x[i]列

int countn;//表示n个皇后可行解的个数

bool place(int t){

bool ok = true;

//判断该位置的皇后是否与前面t-1个已经放置的皇后冲突

for(int j=1; j<t ; j++){

//判断列、对角线是否冲突

if(x[t] == x[j] || t-j == fabs(x[t]-x[j])){

ok=false;

break;

}

}

return ok;

}

void backTrack(int t){

//如果当前位置为n，则表示已经找到了问题的一个解

if(t > n){

countn++;

//打印选择的路径

for(int i=1;i<=n;i++){

printf("%d",x[i]);

printf(" \n");

}

}else{

//分别判断n个分支，特别注意i不要定义为全局变量，否则递归调用有问题

for(int i = 1 ;i<=n;i++){

x[t]=i;

if(place(t)){

//如果不冲突的话进行下一行的搜索

backTrack(t+1);

}

}

}

}

int main()

{

countn=0;

backTrack(1);

cout << "解个数" <<countn<< endl;

return 0;

}