51.N皇后

题目描述

题解

回溯算法

思路就是DFS加剪枝, 碰到不符合要求的行就回退.

比较麻烦的是设置已利用的路径. 如果采用了某一个位置, 那么该行该列该斜方向的位置都不能再放置

一开始打算用一个boolean[n][n]矩阵来表示已经使用过的位置, 但是需要循环将整行的位置改为true, 所以用三个向量分别表示该列, 该主对角线, 该副对角线.

class Solution {
    List<List<String>> res = new ArrayList<>();

    public void test(int n) {
        List<Integer> path = new ArrayList<>();
        boolean[] col = new boolean[n];
        boolean[] main = new boolean[2 * n - 1];
        boolean[] sub = new boolean[2 * n - 1];
        backtrace(n, 0, path, col, main, sub);
    }

    public List<List<String>> solveNQueens(int n) {
        test(n);
        return res;
    }

        private void backtrace(int n, int step, List<Integer> path, boolean[] col, boolean[] main, boolean[] sub) {
        if (step == n) {
            res.add(integerToString(path));
            return;
        }

        for (int i = 0; i < n; i++) {
            if (!col[i] && !main[step - i + n - 1] && !sub[step + i]) {
                path.add(i);
                col[i] = true;
                main[step - i + n - 1] = true;
                sub[step + i] = true;
                backtrace(n, step + 1, path, col, main, sub);

                path.remove(path.size() - 1);
                col[i] = false;
                main[step - i + n - 1] = false;
                sub[step + i] = false;
            }
        }
    }

    private List<String> integerToString(List<Integer> path){
        List<String> strList = new ArrayList<>();
        for (Integer index : path) {
            StringBuilder str = new StringBuilder(".".repeat(path.size()));
            str.replace(index, index+1, "Q");
            strList.add(str.toString());
        }
        return strList;
    }
}