[Leetcode] N-Queens N皇后

摘要：暴力法复杂度时间空间思路因为皇后问题中，同一列不可能有两个皇后，所以我们可以用一个一维数组来表示二维棋盘上皇后的位置。一维数组中每一个值的下标代表着对应棋盘的列，每一个值则是那一列中皇后所在的行。

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens" placement, where "Q" and "." both indicate a queen and an empty space respectively.

For example, There exist two distinct solutions to the 4-queens puzzle:
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

时间 O(N^3) 空间 O(N)

因为n皇后问题中，同一列不可能有两个皇后，所以我们可以用一个一维数组来表示二维棋盘上皇后的位置。一维数组中每一个值的下标代表着对应棋盘的列，每一个值则是那一列中皇后所在的行。这样我们可以只对一个一维数组进行深度优先搜索，来找出对于每一列，我们的皇后应该放在哪一行。在下一轮搜索之前，我们先检查一下新构成的数组是否是有效的，这样可以剪掉不必要的分支。检查的方法则是看之前排好的每一个皇后是否冲突。

public class Solution {
    
    List> res;
    
    public List> solveNQueens(int n) {
        res = new LinkedList>();
        int[] nqueens = new int[n];
        helper(nqueens, n, 0);
        return res;
    }
    
    public void helper(int[] nqueens, int n, int i){
        if(i == nqueens.length){
            List one = new LinkedList();
            // 构成表示整个棋盘的字符串
            for(int num : nqueens){
                // 构成一个形如....Q....的字符串
                StringBuilder sb = new StringBuilder();
                for(int j = 0; j < num; j++){
                    sb.append(".");
                }
                sb.append("Q");
                for(int j = num + 1; j < n; j++){
                    sb.append(".");
                }
                one.add(sb.toString());
            }
            res.add(one);
        } else {
            //选择下一列的数字
            // 比如之前已经选了13xxxxxx，下一列可以选6，形成136xxxxx
            for(int num = 0; num < n; num++){
                nqueens[i] = num;
                // 如果是有效的，继续搜索
                if(isValid(nqueens, i)){
                    helper(nqueens, n, i+1);
                }
            }
        }
    }
    
    private boolean isValid(int[] nqueens, int i){
        for(int idx = 0; idx < i; idx++){
            // 检查对角线只要判断他们差的绝对值和坐标的差是否相等就行了
            if(nqueens[idx] == nqueens[i] || Math.abs(nqueens[idx] - nqueens[i]) ==  i - idx){
                return false;
            }
        }
        return true;
    }
}

时间 O(N^2) 空间 O(N)

该方法的思路和暴力法一样，区别在于，之前我们判断一个皇后是否冲突，是遍历一遍当前皇后排列的列表，看每一个皇后是否冲突。这里，我们用三个集合来保存之前皇后的信息，就可以O(1)时间判断出皇后是否冲突。三个集合分别是行集合，用于存放有哪些行被占了，主对角线集合，用于存放哪个右上到左下的对角线被占了，副对角线集合，用于存放哪个左上到右下的对角线被占了。如何唯一的判断某个点所在的主对角线和副对角线呢？我们发现，两个点的行号加列号的和相同，则两个点在同一条主对角线上。两个点的行号减列号的差相同，则两个点再同一条副对角线上。

主对角线row + col，副对角线row - col

public class Solution {
    
    List> res = new LinkedList>();;
    Set rowSet = new HashSet();
    Set diag1Set = new HashSet();
    Set diag2Set = new HashSet();
    
    public List> solveNQueens(int n) {
        helper(new LinkedList(), n, 0);
        return res;
    }
    
    public void helper(LinkedList tmp, int n, int col){
        if(col == n){
            List one = new LinkedList();
            for(Integer num : tmp){
                StringBuilder sb = new StringBuilder();
                for(int j = 0; j < num; j++){
                    sb.append(".");
                }
                sb.append("Q");
                for(int j = num + 1; j < n; j++){
                    sb.append(".");
                }
                one.add(sb.toString());
            }
            res.add(one);
        } else {
            // 对于列col，看皇后应该放在第几行
            for(int row = 0; row < n; row++){
                int diag1 = row + col;
                int diag2 = row - col;
                // 如果三条线上已经有占据的皇后了，则跳过该种摆法
                if(rowSet.contains(row) || diag1Set.contains(diag1) || diag2Set.contains(diag2)){
                    continue;
                }
                // 用回溯法递归求解
                tmp.add(row);
                rowSet.add(row);
                diag1Set.add(diag1);
                diag2Set.add(diag2);
                helper(tmp, n, col + 1);
                diag2Set.remove(diag2);
                diag1Set.remove(diag1);
                rowSet.remove(row);
                tmp.removeLast();
            }
        }
    }
}

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.

时间 O(N^3) 空间 O(N)

跟I的解法一样，只不过把原本构造字符串的地方换成了计数器加一。

public class Solution {
    
    List> res;
    int cnt = 0;
    
    public int totalNQueens(int n) {
        int[] nqueens = new int[n];
        helper(nqueens, n, 0);
        return cnt;
    }
    
    public void helper(int[] nqueens, int n, int i){
        if(i == nqueens.length){
            cnt++;
        } else {
            for(int num = 0; num < n; num++){
                nqueens[i] = num;
                if(isValid(nqueens, i)){
                    helper(nqueens, n, i+1);
                }
            }
        }
    }
    
    private boolean isValid(int[] nqueens, int i){
        for(int idx = 0; idx < i; idx++){
            if(nqueens[idx] == nqueens[i] || Math.abs(nqueens[idx] - nqueens[i]) ==  i - idx){
                return false;
            }
        }
        return true;
    }
}

时间 O(N^2) 空间 O(N)

跟I的解法一样，只不过把原本构造字符串的地方换成了计数器加一。

public class Solution {
    
    Set rowSet = new HashSet();
    Set diag1Set = new HashSet();
    Set diag2Set = new HashSet();
    int cnt = 0;
    
    public int totalNQueens(int n) {
        helper(n, 0);
        return cnt;
    }
    
    public void helper(int n, int col){
        if(col == n){
            cnt++;
        } else {
            for(int row = 0; row < n; row++){
                int diag1 = row + col;
                int diag2 = row - col;
                if(rowSet.contains(row) || diag1Set.contains(diag1) || diag2Set.contains(diag2)){
                    continue;
                }
                rowSet.add(row);
                diag1Set.add(diag1);
                diag2Set.add(diag2);
                helper(n, col + 1);
                diag2Set.remove(diag2);
                diag1Set.remove(diag1);
                rowSet.remove(row);
            }
        }
    }
}