题目描述

N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后， 要求：任何两个皇后不同行，不同列也不再同一条斜线上， 求给一个整数 n ，返回 n 皇后的摆法数。

题目分析

对于n皇后的放置，主要有三个放置要求（不同行、不同列、不同斜线），可以先考虑不同行的情况，即在每一行只选择一个位置，记录上前面的位置，后面选择位置只需要判断另外的两个方向，对于排列枚举的情况，一共有n!种。

可以遍历枚举的所有情况，当满足三个条件的结果出现时，方法数加1。

解题思路

遍历枚举的情况的过程就是dfs的过程，从第1行开始，每行可以从1~n列中选择一个作为放置位置，只要不和前面冲突，可以继续下一行的选择，直到所有行都选择完成，即为一种方法。

代码实现

方法1：dfs深度遍历，使用二维数组记录之前的位置

    int num = 0;
    public int Nqueen (int n) {
        // write code here
        // 表示皇后所放的位置
        boolean[][] flag = new boolean[n][n];
        // 从第一行开始放置
        dfs(flag, 0);
        return num;
    }
    
    public void dfs(boolean[][] flag, int start){
        if(start == flag.length){
            num++;
            return;
        }
        // 确定每一行的列的位置
        for(int j=0;j<flag.length;j++){
            if(isValid(flag, start, j)){
                flag[start][j] = true;
                dfs(flag, start+1);
                flag[start][j] = false;
            }
        }
    }
    
    public boolean isValid(boolean[][] flag, int row, int col){
        // 判断是否有重列的
        for(int i=0;i<row;i++){
            int ls = col-row+i;
            int rs = row+col-i;
            if(flag[i][col] || (ls<col && ls>=0 && flag[i][ls]) || (rs>=col && rs<flag.length && flag[i][rs])){
                return false;
            }
        }
        return true;
    }

时间复杂度：$O(n!n)O(n!\; n)$O(n!n)，在遍历过程中，至少需要遍历n!种情况，每种情况最多需要判断n-1次是否合法，花费时间复杂度为O(n)。

空间复杂度：$O\left(n^2\right)O(n^2)$O(n2)，需要额外的空间数组flag[n][n] 来保存之前访问过的位置。

方法2（优化方法1的空间）：使用set记录走过的位置

    int num = 0;
    public int Nqueen (int n) {
        // 表示皇后所放的位置
        // 使用三个集合来存储之前的列和对角线信息
        Set<Integer> columns = new HashSet<Integer>();
        Set<Integer> diagonals1 = new HashSet<Integer>();
        Set<Integer> diagonals2 = new HashSet<Integer>();
        dfs(0, n, columns, diagonals1, diagonals2);
        return num;
    }
    
    public void dfs(int start, int n, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2){
        // 前n行都分配完成，增加一种方法
        if(start == n){
            num++;
            return;
        }
        // 确定每一行的列的位置
        for(int j=0;j<n;j++){
            // 左上对角线坐标
            int ls = start-j;
            // 右上对角线坐标
            int rs = start+j;
            // 判断前i行的是否有列、对角线重叠
            if(!columns.contains(j) && !diagonals1.contains(ls) && !diagonals2.contains(rs)){
                columns.add(j);
                diagonals1.add(ls);
                diagonals2.add(rs);
                dfs(start+1, n, columns, diagonals1, diagonals2);
                columns.remove(j);
                diagonals1.remove(ls);
                diagonals2.remove(rs);
            }
        }
    }

时间复杂度：$O(n!3n)O(n!\; 3n)$O(n!3n)，在遍历过程中，至少需要遍历n!种情况，使用hashset在判断上最差需要O(n)时间（数据在同一个链表上），同时因为不断地对set进行add和remove，最差情况花费的时间复杂度也是O(n)。

空间复杂度：$O\left(n\right)O(n)$O(n)，在存储之前的位置的时候，可以只需要记录存下来的位置，减少空余位置，使用的三个set最多存储3n的数据。