经典算法问题之八皇后

                                     八皇后问题                     

八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种方法可以解决此问题。

           用回溯法解决该问题： G++：
          刚开始看到这个问题，会想到遍历，但是仔细想想会发现太复杂了，其实一个个皇后排的话，你会

发现前几列不能满足了，后面的就都不行了，所以我们要用回溯法倒回去，解决这种问题最好是用递归，

简洁，明了。

           变量的定义：

           

#include<iostream>
using namespace std ;
#define NUM 9
static int a[NUM] ;//创建数组
int count=0 ;//计数

          

          判断本列的这个皇后能否满足情况：

   

bool judgeQueen(int index,int value)
{
    int i,j,data;
    for(i=1;i<index;i++)
    {
       data = a[i] ;
       if(data == value)  return 0 ; //列相等
       if((data-i)==(value-index)) return 0 ;//负斜一条线
       if((data+i)==(value+index)) return 0 ;//正邪一条线
    }
   return true ;
}

 
           递归算法实现：

      

void InitQueen(int index)
{
    int i,j ;
   for(i=1;i<9;i++){
    if(judgeQueen(index,i))//这列能放下皇后
     {
         a[index] = i ;
         if(index == 8) //这种摆法能成功
         {
             count++ ;
             a[index] = 1 ;
             continue  ;
         }
         InitQueen(index + 1) ;//继续递归
         a[index] = 1 ;
     }
   }
}

     解决方法二： Java

     声明变量：

    

// 同栏是否有皇后，1表示有     
private int[] column;     
// 右上至左下是否有皇后     
private int[] rup;     
// 左上至右下是否有皇后     
private int[] lup;    
// 解答     
private int[] queen;          
// 解答编号     
private int num;  

   

    构造方法初始化：

    

public Queen() {         
		column = new int[8+1];        
		rup = new int[2*8+1];         
		lup = new int[2*8+1];                   
		for(int i = 1; i <= 8; i++)             
			column[i] = 1;          
		for(int i = 1; i <= 8; i++)             
			rup[i] = lup[i] = 1;                   
		queen = new int[8+1];     
		}      

  

   回溯方法：

   

public void backtrack(int i) {         
		if(i > 8) {             
			showAnswer();        
			}         
		else {             
			for(int j = 1; j <= 8; j++) {                
				if(column[j] == 1 &&                    
						rup[i+j] == 1 &&                   
						lup[i-j+8] == 1) {                     
					queen[i] = j;                     
					// 设定为占用                     
					column[j] = rup[i+j] = lup[i-j+8] = 0;                    
					backtrack(i+1);                    
					column[j] = rup[i+j] = lup[i-j+8] = 1;                
					}             
				}        
			}     
		}