八皇后算法详解

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)是否是安全位置的算法：

//判断位置(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列后的皇后摆放方法:在第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("不能完成棋局，棋局失败！");

			}
			
		}
	}

  

 

评论

2 楼 mars914 2012-03-15  

/*
改进后的八皇后解法
效率高了很多
*/
#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;
}

1 楼 mars914 2012-03-15  

package com.java.algorithm;

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);  
    }  
}