51. N-Queens.md

LeetCode 51. N-Queens

思路

N皇后问题，经典的回溯法问题。回溯法无外乎分清状态，维护好路径，分清选择和结束条件。

模板如下：

# 回溯法模板
def backtrack(路径，状态):
  if 满足结束条件:
    记录当前的路径
    return
  for 选择 in 所有的选择:
    尝试该选择（添加到路径中）
    backtrack(新路径，新状态)
    撤销该选择
    

解法一 回溯法

时间复杂度：$O(N^N)$，虽然有$isValid()$剪枝

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<>();
        if (n == 0)
            return solutions;

        List<String> board = new ArrayList<>(n);
        backtrack(board, 0, n, solutions);
        return solutions;
    }

    private static void backtrack(List<String> board, int row, int n, List<List<String>> solutions) {
        if (row == n) {
            solutions.add(new ArrayList<>(board));
            return;
        }

        for (int col = 0; col < n; col++) {
            if (!isValid(board, row, col, n)) 
                continue;
            board.add(placeQueen(n, col));
            backtrack(board, row+1, n, solutions);
            board.remove(board.size()-1);
        }
    }

    private static boolean isValid(List<String> board, int row, int col, int n) {
        Character queen = 'Q';
        // examine column
        for (int i = 0; i < row; i++) 
            if (queen.equals(board.get(i).charAt(col)))
                return false;
        
        // examine left top in the diagnoal
        for (int i = row-1, j = col-1; i >= 0 && j >= 0; i--, j--)
            if (queen.equals(board.get(i).charAt(j)))
                return false;
        
        // examine right top in the diagnoal
        for (int i = row-1, j = col+1; i >= 0 && j < n; i--, j++)
            if (queen.equals(board.get(i).charAt(j)))
                return false;
        
        return true;
    }

    private static String placeQueen(int n, int col) {
        StringBuilder s = new StringBuilder();
        for (int i = 0; i < col; i++)
            s.append(".");
        s.append("Q");
        for (int i = col+1; i < n; i++)
            s.append(".");
        return s.toString();
    }
}

运行时间9ms

解法二 优化版本

优化思路：解法一在每一层搜索时都从头搜到尾，然而我们知道N皇后不能见面，因此之前的行放过的皇后所在的列已经不能再放了，因此在每一层的搜索时，完全可以用一个数据结构（数组）保存之前已经放置过皇后的列，如此时间复杂度可以大大缩减（空间换时间）。

此时时间复杂度: $O(N!)$（第1行最多N个选择，第2行N-1个选择）。

此外，还可以先用一个数组保存当前的皇后的选择（索引做行，数组保存列位置），到最后再转化为字符串添加到结果中，减少开销。

如何快速判断一个位置是否有效，还可以用三个HashSet分别记录某一列，以及两个方向的每条斜线上。记录列只需记录列号，主对角线行下标与列下标之差为定值，副对角线行下标与列下标之和为定值（类似直线）

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<>();

        int[] board = new int[n];
        Arrays.fill(board, -1);
        Set<Integer> illegalCols = new HashSet<>(); // save column index
        Set<Integer> illegalDiag1 = new HashSet<>(); // save difference between row index and column index
        Set<Integer> illegalDiag2 = new HashSet<>(); // save the sum of them
        backtrack(board, 0, n, solutions, illegalCols, illegalDiag1, illegalDiag2);

        return solutions;
    }

    static void backtrack(int[] board, int row, int n, List<List<String>> solutions, Set<Integer> illegalCols, Set<Integer> illegalDiag1, Set<Integer> illegalDiag2) {
        if (row == n) {
            solutions.add(generateSolution(board, n));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (illegalCols.contains(i))
                continue;
            int diff = row - i;
            if (illegalDiag1.contains(diff))
                continue;
            int sum = row + i;
            if (illegalDiag2.contains(sum))
                continue;
            
            board[row] = i;
            illegalCols.add(i);
            illegalDiag1.add(diff);
            illegalDiag2.add(sum);
            backtrack(board, row+1, n, solutions, illegalCols, illegalDiag1, illegalDiag2);
            illegalDiag2.remove(sum);
            illegalDiag1.remove(diff);
            illegalCols.remove(i);
            board[row] = -1;
        }
    }

    static List<String> generateSolution(int[] board, int n) {
        List<String> aSolution = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            aSolution.add(generateString(board[i], n));
        }
        return aSolution;
    }

    static String generateString(int col, int n) {
        char[] aRow = new char[n];
        Arrays.fill(aRow, '.');
        aRow[col] = 'Q';
        return new String(aRow);
    }
}

运行时间6ms

解法三 用移位运算优化

运行时间 2ms

--摘自LeetCode该题的官方解法

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<>();
        int[] columns = new int[n];
        Arrays.fill(columns, -1);

        backtrack(solutions, 0, n, columns, 0, 0, 0);
        return solutions;
    }

    private static void backtrack(List<List<String>> solutions, int row, int n, int[] columns, int illegalCols, int illegalDiag1, int illegalDiag2) {
        if (row == n) {
            solutions.add(generateSolution(columns, n));
            return;
        }

        illegalDiag1 <<= 1;
        illegalDiag2 >>>= 1;
        int legalPos =  (1<<n) - 1 & ~(illegalCols | illegalDiag1 | illegalDiag2);
        for (int i = 0; i < n && legalPos > 0; i++, legalPos >>>= 1)  {
            if ((legalPos & 1) == 0)
                continue;
            columns[row] = i;
            illegalCols = illegalCols | (1<<i);
            illegalDiag1 = illegalDiag1 | (1<<i);
            illegalDiag2 = illegalDiag2 | (1<<i);
            backtrack(solutions, row+1, n, columns, illegalCols, illegalDiag1, illegalDiag2);
            illegalDiag2 = illegalDiag2 & ~(1<<i);
            illegalDiag1 = illegalDiag1 & ~(1<<i);
            illegalCols = illegalCols & ~(1<<i);
            columns[row] = -1;
        }
    }

    private static List<String> generateSolution(int[] columns, int n) {
        List<String> board = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            char[] aRow = new char[n];
            Arrays.fill(aRow, '.');
            aRow[columns[i]] = 'Q';
            board.add(new String(aRow));
        }
        return board;
    }
}

小结

回顾这道题，拿到这道题的时候，其实我们很容易看出需要使用枚举的方法来求解这个问题，当我们不知道用什么办法来枚举是最优的时候，可以从下面三个方向考虑：

• 子集枚举：可以把问题转化成「从 $n^2$个格子中选一个子集，使得子集中恰好有 $n$ 个格子，且任意选出两个都不在同行、同列或者同对角线」，这里枚举的规模是 $2^{n^2} $
• 组合枚举：可以把问题转化成「从 $n^2 $个格子中选择 $n$ 个，且任意选出两个都不在同行、同列或者同对角线」，这里的枚举规模是 ${n^2} \choose {n}$
• 排列枚举：因为这里每行只能放置一个皇后，而所有行中皇后的列号正好构成一个 1到 n的排列，所以我们可以把问题转化为一个排列枚举，规模是 $n!$。

带入一些 $n$ 进这三种方法验证，就可以知道哪种方法的枚举规模是最小的，这里我们发现第三种方法的枚举规模最小。这道题给出的两个方法其实和排列枚举的本质是类似的。

作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/n-queens/solution/nhuang-hou-by-leetcode-solution/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。