题解 | #N皇后问题#TOP59

如果皇后出现在第一列，那么第一行的皇后位置就确定了，接下来递归地在剩余的n−1行中找n−1个皇后的位置。
固定一个[i,j]，那接下来的第j+1列，尝试选择n种位置，每一行都递归尝试，反之亦然，但是在每次尝试j+1列，不同行的位置时，是不是要将这一列都清空。

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 the n
     * @return int整型
     */
    public int Nqueen (int n) {
        // write code here
        if(n <= 0){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        if(n == 2 ||n == 3){
            return 0;
        }
        //二维数组
        int[][] dp = new int[n][n];
        int  y = 0;
        return settleQueue(y,dp);
        
    }
    private int settleQueue(int y, int[][] dp){
        if(y == dp.length){
            //行数
            return 1;
        }
        int n = dp.length;
        int num = 0;
        for(int i = 0;i < n; i++){
            //当前列清0
            for(int x = 0; x < n ; x++){
                dp[x][y] = 0;
            }
            //检查是否合规
            if(check(i, y , dp)){
                dp[i][y] = 1;
                num += settleQueue(y +1, dp);
            }
        }
        return num;
    }
    private boolean check(int x, int y , int[][] dp){
        //横向遍历
        for(int i = 0; i< y; i++){
            //[x, y] 的一行上是否有==1的数
            if(dp[x][i] == 1){
                return false;
            }
            //判断[x,y]位置上的左上角斜线位置是否有1
            if(x - 1 - i >= 0 && dp[x -1 -i][y-1-i] == 1){
                return false;
            }
            //[x,y]左下角斜线是否有1
            if(x + 1 + i < dp.length && dp[x+1+i][y-1-i] == 1){
                return false;
            }
        }
        return true;
    }
}