N皇后问题

时间限制: 5秒  内存限制: 64M

N皇后问题是一个古老而经典的题目。该问题源自数学家高斯1850年提出八皇后问题：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任 意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

例如，在一个4x4的棋盘上，摆放4个皇后有两种方法，

用文本方式输出为

* Q * *
* * * Q
Q * * *
* * Q *

* * Q *
Q * * *
* * * Q
* Q * *

我们可以用一维整数数组Q[]来表示N个皇后的摆放位置，例如，对4皇后问题的第一个解可以表示 为，Q[0]=1,Q[1]=3,Q[2]=0,Q[3]=2。

当我们逐渐往棋盘上放置皇后时，用这种表示方法，可以做如下的判断来检查新放入的皇后的位置k是否可行：

1、如果Q[i]==Q[k]，则有两个皇后在同一列，不可行；

2、如果Q[i]-Q[k]==(i-k)，则有两个皇后在对角线上相互攻击，不可行；

3、如果Q[k]-Q[i]==(i-k)，则有两个皇后在反对角线上相互攻击，不可行；

本题要求你按顺序输出N皇后问题的解。

 

输入：

棋盘的阶数N

输出：

对应的N皇后问题的解，请按照顺序输出。顺序可参考后面给出的参考解答。

 

样例输入：

4

样例输出：

*□ Q□ *□ *□ ↵

*□ *□ *□ Q□ ↵

Q□ *□ *□ *□ ↵

*□ *□ Q□ *□ ↵

↵

*□ *□ Q□ *□ ↵

Q□ *□ *□ *□ ↵

*□ *□ *□ Q□ ↵

*□ Q□ *□ *□ ↵

↵

 

import java.util.Scanner;

 public class Main{     
	 public static boolean Place(int Q[],int k) //考察皇后k放置在Q[k]列是否发生冲突    
	 {     
	     for(int i=1; i<k; i++)        
	     {     
	    	 if (Q[i]==Q[k]||Q[i]-Q[k]==(i-k)||Q[k]-Q[i]==(i-k))      
	        	 return false;     
	     	 }     
	         return true;     
	     }     
	     public static void Queen(int n)     
	     {     
	    	 int Q[]=new int[n+1];     
	         for (int i=1; i<=n; i++)//初始化     
	             Q[i]=0;     
	         int k=1;     
	         while (k>=1)     
	         {     
	             Q[k]=Q[k]+1;//在下一列放置第k个皇后     
	          while (Q[k]<=n&&!Place(Q,k))      
	              Q[k]=Q[k]+1;//如果不符合条件，搜索下一列     
	          if (Q[k]<=n && k==n)     
	          {       
	              boolean[][] bl = new boolean[n][n];     
	              for (int i=1; i<=n; i++){       
	                  bl[i-1][Q[i]-1]=true;     
	              }     
	              for(int l=1;l<=n;l++){     
	                  for(int c=1;c<=n;c++){     
	                      if(bl[l-1][c-1]==true)     
	                          System.out.print("Q ");     
	                      else    
	                    	  System.out.print("* ");     
	                  }     
	                  System.out.println();     
	              }     
	           System.out.println();     
	          }      
	          else if (Q[k]<=n && k<n)     
	        	  k=k+1;     //放置下一个皇后
	          else {      
	              Q[k]=0;     //重置Q[k]，回溯
	              k=k-1;     
	          }     
	         }     
	       }    
	       public static void main(String[] args)     
	       {      
	    	   Scanner scanner = new Scanner(System.in);
	    	   int n = scanner.nextInt();
	           Queen(n);     
	       }     
	   } 

 

附上论坛里最快的解法：http://www.iteye.com/topic/20059