N后问题 Java版

墨蓝 2022-08-18 03:05 41阅读 0赞

/\*  
*//\**  
\* N皇后问题

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 14577 Accepted Submission(s): 6646

Problem Description  
在N\*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，  
也不允许处在与棋盘边框成45角的斜线上  
你的任务是，对于给定的N，求出有多少种合法的放置方法。

Input  
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。

Output  
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

Sample Input  
1  
8  
5  
0

Sample Output  
1  
92  
10

*  题目要求中的不准放在与棋盘边框成45度角的斜线上，可以视为是主对角线及副对角线及其所有平行线上不能有两个皇后

import java.util.Arrays;
    import java.util.Calendar;
    import java.util.Scanner;
    
    import javax.swing.Box.Filler;
    
    public class Main {
        static int N,res;
        static int[][] chessboard = new int [11][11];
        static boolean debug = false;
        static void Print(){
            System.out.println("Output chessboard:");
            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++) System.out.print(chessboard[i][j]+" ");
                System.out.println();
            }
            return ;
        }
        static boolean judge(int x,int y){
            for(int i=0;i<N;i++){
                if(chessboard[i][y]==1) return false;
            }
            for(int i=0;i<N;i++){
                if(chessboard[x][i]==1) return false;
            }
            //所谓的与边框成45度，即两个点之间斜率为-1或1.
            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    if((x+y==i+j||i-j==x-y)&&chessboard[i][j]==1) return false;
                }
            }
            return true;
        }
        //从前至后开始放。
        static void dfs(int r){
            if(debug) System.out.println("test,r:"+r);
            if(r>=N){
       //所有行都放上了,注意边界条件，棋子是从0行开始放的
                res++;
            // Print();
                return ;
            }
            for(int c=0;c<N;c++){
       //第r行有N中可能放皇后的位置
                //chessboard[r][c] = 1;
                if(judge(r,c)){
       //先判断再放
                    chessboard[r][c] = 1;
                    dfs(r+1);
                    chessboard[r][c] = 0;
                }
                //chessboard[r][c] = 0;
            }
            return ;
        }
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner cin = new Scanner(System.in);
            while(cin.hasNext()){
                long start=Calendar.getInstance().getTimeInMillis();
                N = cin.nextInt();
                if(N==0) break;
                for(int[] row:chessboard) Arrays.fill(row, 0);//给数组所有元素赋值0用以标记
                res = 0;
                dfs(0);
                long end=Calendar.getInstance().getTimeInMillis();
                System.out.println("Time cost:"+(end-start)+"\n"+res);
    
            }
        }
    
    }

//上述代码会超时，直接根据上述代码得到所有答案，输出！

import java.util.*;
    
    import javax.swing.text.html.CSS;
    public class Main{
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner cin = new Scanner(System.in);
            while(cin.hasNext()){
                long start=Calendar.getInstance().getTimeInMillis();
                int N = cin.nextInt();
                if(N==0) break;
                int res=0;
                switch (N) {
                case 1:
                    res = 1;
                    break;
                case 3:
                case 2:
                    res = 0;
                    break;
                case 4:
                    res = 2;
                    break;
                case 5:
                    res = 10;
                    break;
                case 6:
                    res = 4;
                    break;
                case 7:
                    res = 40;
                    break;
                case 8:
                    res = 92;
                    break;
                case 9:
                    res = 352;
                    break;
                case 10:
                    res = 724;
                    break;
                default:
                    break;
                }
                System.out.println(res);
            }
        }
    }