N皇后问题

package cn.gao.algorithm2.service;

/*
 * 经典的八皇后问题（恒生电子笔试B卷最后一题,当初哥用8个for循环，真汗颜，无脸面江东父老。。。）
 * 八皇后问题是一个古老而著名的问题，是递归中回溯算法的典型例题。在8X8格的国际象棋上摆放八个皇后，
 * 使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一正反斜线上，问有多少种摆法。
 * 这里将八皇后推广位N皇后问题NightQueueTest类实现此功能
 * 
 * 解决思想：
 * 构建规则函数，判断在某列col中,行为row的元素是否"碰撞"过原来的元素，即与之前的0-col-1咧的每个元素都不会在同一行，同一列，同一正反斜线上相遇
 * 构建通路函数：判断某列col中，能不能走通，即判断到第8列且第8列是符合前面规则的.
 * 
 */
public class NightQueueTest {
	/*判断规则函数，判断某个列是否'碰撞'过之前的数据*/
	public int queenList[];/*记录皇后数组，下标表示列，值表示列所对应的行*/
	public int count;/*统计路径方案种数*/
	public int n;/*皇后问题规模*/
	
     public NightQueueTest(int n) {/*初始一个N规模的皇后问题*/
		super();
		this.queenList = new int[n];
		this.count = 0;
		this.n=n;
	}
	public boolean check(int col,int row)/*判断之前列的点与当前点不在同一行，同一正反斜线上*/
     {
    	 for(int i=0;i<col;i++)
    	 {
    		 if(queenList[i]==row||(queenList[i]+i==row+col)||(queenList[i]-i==row-col))
    		 {			
    			return false; 
    		 }
    	 }
    	 return true;
     }
     public void findCorrectPath(int col)/*判断第col列是否能够走通，即当前第col列到第8列都能够走通*/
     {
    	 if(col==this.n)/*前面0-7个都已经遍历完毕，所以如果到了col=8，说明前面7个都正确，表示整个路径分布成功了*/
    	 {
    		 count++;
    		 System.out.println("第"+count+"种方案:");
    		 for(int i=0;i<queenList.length;i++)/*打印已有方案*/
    		 {
    			System.out.println("第"+i+"列"+"第"+queenList[i]+"行："+"第"+(i+1)+"个皇后"); 
    		 }
    		 System.out.println("\n\n");
    		 return ;
    	 }
    	 else{
    		 int row=0;
    		  while(row<this.n)
    		  {
    			  if(check(col,row))/*当前第col列选取的第row行是符合规则的*/
    			  { 
    				  //System.out.println("aaaa:"+count+":  "+col+row);
    				  queenList[col]=row;/*有点进栈的味道*/
    				  findCorrectPath(col+1);
    				  queenList[col]=0;/*有点出栈的味道*/
    			  }
    			 row++;
    		  }
    		 
    	 }
     }
	public static void main(String[] args) {
	
		NightQueueTest gao=new NightQueueTest(8);
		gao.findCorrectPath(0);
	}

}