8皇后算法详解
1.引子
中国有一句古话,叫做“不撞南墙不回头",生动的说明了一个人的固执,有点贬义,但是在软件编程中,这种思路确是一种解决问题最简单的算法,它通过一种类似于蛮干的思路,一步一步地往前走,每走一步都更靠近目标结果一些,直到遇到障碍物,我们才考虑往回走。然后再继续尝试向前。通过这样的波浪式前进方法,最终达到目的地。当然整个过程需要很多往返,这样的前进方式,效率比较低下。
2.适用范围
适用于那些不存在简明的数学模型以阐明问题的本质,或者存在数学模型,但是难于实现的问题。
3.应用场景
在8*8国际象棋棋盘上,要求在每一行放置一个皇后,且能做到在竖方向,斜方向都没有冲突。国际象棋的棋盘如下图所示:
4.分析
基本思路如上面分析一致,我们采用逐步试探的方式,先从一个方向往前走,能进则进,不能进则退,尝试另外的路径。首先我们来分析一下国际象棋的规则,这些规则能够限制我们的前进,也就是我们前进途中的障碍物。一个皇后q(x,y)能被满足以下条件的皇后q(row,col)吃掉
1)x=row(在纵向不能有两个皇后)
2) y=col(横向)
3)col + row = y+x;(斜向正方向)
4) col - row = y-x;(斜向反方向)
遇到上述问题之一的时候,说明我们已经遇到了障碍,不能继续向前了。我们需要退回来,尝试其他路径。
我们将棋盘看作是一个8*8的数组,这样可以使用一种蛮干的思路去解决这个问题,这样我们就是在8*8=64个格子中取出8个的组合,C(64,80) = 4426165368,显然这个数非常大,在蛮干的基础上我们可以增加回溯,从第0列开始,我们逐列进行,从第0行到第7行找到一个不受任何已经现有皇后攻击的位置,而第五列,我们会发现找不到皇后的安全位置了,前面四列的摆放如下:
第五列的时候,摆放任何行都会上图所示已经存在的皇后的攻击,这时候我们认为我们撞了南墙了,是回头的时候了,我们后退一列,将原来摆放在第四列的皇后(3,4)拿走,从(3,4)这个位置开始,我们再第四列中寻找下一个安全位置为(7,4),再继续到第五列,发现第五列仍然没有安全位置,回溯到第四列,此时第四列也是一个死胡同了,我们再回溯到第三列,这样前进几步,回退一步,最终直到在第8列上找到一个安全位置(成功)或者第一列已经是死胡同,但是第8列仍然没有找到安全位置为止
总结一下,用回溯的方法解决8皇后问题的步骤为:
1)从第一列开始,为皇后找到安全位置,然后跳到下一列
2)如果在第n列出现死胡同,如果该列为第一列,棋局失败,否则后退到上一列,在进行回溯
3)如果在第8列上找到了安全位置,则棋局成功。
8个皇后都找到了安全位置代表棋局的成功,用一个长度为8的整数数组queenList代表成功摆放的8个皇后,数组索引代表棋盘的col向量,而数组的值为棋盘的row向
量,所以(row,col)的皇后可以表示为(queenList[col],col),如上图中的几个皇后可表示为:
queenList[0] = 0; queenList[1] = 3; queenList[2] = 1; queenList[3] = 4; queenList = 2;
我们看一下如何设计程序:
首先判断(row,col)是否是安全位置的算法:
设定一个函数,用于查找col列后的皇后摆放方法://判断位置(row,col)是否是安全的
boolean isSafe(int col,int row,int[] queenList){
//只检查前面的列
for(int tempCol=0;tempCol<col;tempCol++){
int tempRow=queenList[tempCol];
if(tempRow==row){
//同一行
return false;
}
if(tempCol==col){
//同一列
return false;
}
if((tempRow-tempCol==row-col)||(tempRow+tempCol==row+col)){
return false;
}
}
return true;
}
/**查找col列后的皇后摆放方法:在第col列寻找安全的row值 * @param queenList * @param col * @return * */ public boolean placeQueen(int[] queenList,int col){ int row=0; boolean foundSafePos=false; if(col==8){ //处理完第8列的完成 foundSafePos=true; }else{ while(col<8&&!foundSafePos){ if(isSafe(col,row,queenList)){ //找到安全位置 queenList[col]=row; //找下一个安全位置 foundSafePos=placeQueen(queenList,col+1); if(!foundSafePos){ row++; } }else{ row++; } } } return foundSafePos; }
主函数:
public static void main(String[] args) { EightQueen eq=new EightQueen(); int[] queenList=new int[8]; for(int j=0;j<8;j++){ System.out.println("----------------"+j+"----------------"); queenList[0]=j; boolean res=eq.placeQueen(queenList, 1); if(res){ System.out.print(" "); for(int i=0;i<8;i++){ System.out.print(" "+i+" "); } System.out.println(""); for (int i = 0; i < 8; i++){ System.out.print(+i+""); for (int a = 0; a < 8; a++){ if (i == queenList[a]){ System.out.print(" q "); } else{ System.out.print(" * "); } } System.out.println(""); } System.out.println("---------------------------------------"); }else{ System.out.println("不能完成棋局,棋局失败!"); } } }
public class EightEmpress {
private int n ; //皇后个数
private int[] x ; //当前解
private long sum ; //当前已找到的可行方案数
private static int h ; //记录遍历方案序数
public EightEmpress(){
this.sum = 0 ; //初始化方案数为1,当回溯到最佳方案的时候,就自增1
this.n = 8 ; //求n皇后问题,由自己定义
this.x = new int[n+1]; //x[i]表示皇后i放在棋盘的第i行的第x[i]列
h = 1 ; //这个是我额外定义的变量,用于遍历方案的个数,请看backTrace()中h变量的作用,这里将它定义为static静态变量
}
public boolean place (int k){
for (int j = 1 ; j < k ; j++){
//这个主要是刷选符合皇后条件的解,因为皇后可以攻击与之同一行同一列的或同一斜线上的棋子
if ( (Math.abs(k - j)) == (Math.abs(x[j]-x[k])) || (x[j] == x[k]) ){
return false ; //如果是与之同一行同一列的或同一斜线上的棋子,返回false;
}
}
return true ;//如果不是与之同一行同一列的或同一斜线上的棋子,返回true;
}
public void backTrace (int t){
if (t > n){ //当t>n时,算法搜索到叶节点,得到一个新的n皇后互不攻击放置方案,方案数加1
sum ++ ; //方案数自增1
System.out.println ("方案" + (h++) + "");
print(x);
System.out.print ("\n----------------\n");//华丽的分割线
}else { //当t<=n时,当前扩展的结点Z是解空间中的内部结点,该节点有x[i]=1,2,…,n共n个子结点,
//对于当前扩展结点Z的每一个儿子结点,由place()方法检测其可行性,
//并以深度优先的方式递归地对可行子树搜索,或剪去不可行子数
for (int i = 1 ; i <= n ; i++){
x[t] = i ;
if (place (t)){ //检查结点是否符合条件
backTrace (t+1); //递归调用
}
}
}
}
public void print (int[] a){ //打印数组,没啥的
for (int i = 1 ; i < a.length ; i++){
System.out.print ("皇后" + i + "在" + i + "行" +a[i] + "列、");
}
}
public static void main (String[] args){
EightEmpress em = new EightEmpress();
em.backTrace(1); //从1开始回溯
System.out.println ("\n详细方案如上所示,"+"可行个数为:" + em.sum);
}
}
改进后的八皇后解法
效率高了很多
*/
#include<iostream>
#include<cmath>
using namespace std;
int queen[10];
bool legal(int depth,int n)//判断该位置(depth行n列)是否可放置一个皇后
{
int i;
for(i=1;i<depth;i++)
if(n==queen[i]||((int)fabs((double)n-(double)queen[i])==depth-i))//判断对角线及列上是否有皇后
return false;
return true;
}
void print()//输出结果
{
int i;
for(i=1;i<=8;i++)
cout<<queen[i];
cout<<endl;
}
void DFS(int depth)
{
if(depth>8) return;//八个都已经放置完毕返回
int i;
for(i=1;i<=8;i++)//扫描depth行上的每一列
{
if(legal(depth,i))//如果可以放置
{
queen[depth]=i;//标记
DFS(depth+1);//放置下一个皇后
if(depth==8)//放置完毕
print();//输出
}
}
}
int main()
{
freopen("output.txt","w",stdout);
DFS(1);//从第一行开始输出
return 0;
}