在N*N的方格棋盘放置了N个皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在与棋盘边框成45角的斜线上。 你的任务是,对于给定的N,求出有多少种合法的放置方法。
Input 共有若干行,每行一个正整数N≤10,表示棋盘和皇后的数量;如果N=0,表示结束。 Output 共有若干行,每行一个正整数,表示对应输入行的皇后的不同放置数量。 Sample Input 1 8 5 0 Sample Output 1 92 10 n皇后问题困扰了我很长时间,在此做一下详细的说明,题目要求任意两个皇后不允许在同一排,同一列,也不允许处在与期盼边框成45角的斜线上;在理解之后发现,此题的主要问题在于:如何控制皇后不在同一行同一列及其对角线上,接下来,我就详细说明一下: 首先按照以前的思路,我会先设置一个boolean数组,用来存储当前列是否已有皇后,但在后续过程中发现这种方法不太容易控制皇后是否在对角线上,所以下面就借鉴一下大佬的思路; 设置三个一维数组分别用来说明皇后是否在同一列,左上到右下的对角线及右上到左下的对角线;如果有皇后,则置1; 在做题的过程中容易对对角线上的控制存在疑惑; 接下来,我来进行陈述: 如果是左下至右上的对角线:那么行号与列号相加为一固定值,可以通过此判断,确定是否有皇后在对角线上 如果是左上至右下的对角线:则行号减列号为一固定值; 附上我的ac代码:
package aa; import java.util.Scanner; public class Main { private static int n; private int[] column; private int[] rup; private int[] lup; private static int[] qq; private static int sum=0; public Main() { column=new int[n]; rup=new int[2*n-1]; lup=new int[2*n-1]; for(int i=0;i<n;i++) { column[i]=0; } for(int i=0;i<(2*n-1);i++) { rup[i]=lup[i]=0; } } private void dfs(int i) { // TODO Auto-generated method stub if(i>(n-1)) { sum++; }else { for(int j=0;j<n;j++) { if((column[j]==0)&&(rup[i+j]==0)&&(lup[i-j+(n-1)]==0)) { column[j]=rup[i+j]=lup[i-j+(n-1)]=1; dfs(i+1); column[j]=rup[i+j]=lup[i-j+(n-1)]=0; } } } } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); qq=new int[11]; for(int i=0;i<11;i++) { qq[i]=-1; } while(sc.hasNext()) { sum=0; n=sc.nextInt(); if(n==0) break; else { if(qq[n]==-1) { Main queen=new Main(); queen.dfs(0); qq[n]=sum; } System.out.println(qq[n]); } } } }