八皇后00

题目链接

八皇后

题目描述

注意点

每个皇后都不同行、不同列，也不在对角线上
“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线

解答思路

本题与N皇后相同，思路仍然是深度优先遍历的同时存储前面每一行选取了哪些列，保证本行选取的列不与前面行有同一列或者在对角线的情况

代码

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        List<Integer> visitedCol = new ArrayList<>();
        dfs(n, 0, visitedCol, res);
        return res;
    }

    public void dfs(int n, int row, List<Integer> visitedCol, List<List<String>> res) {
        if (row >= n) {
            List<String> sonRes = fillSonRes(visitedCol, n);
            res.add(new ArrayList<>(sonRes));
            return;
        }
        for (int col = 0; col < n; col++) {
            // 该列已经有皇后
            if (visitedCol.contains(col)) {
                continue;
            }
            // 对角线是否有皇后
            if (isDialog(visitedCol, row, col)) {
                continue;
            }
            // 该位置可以放皇后
            visitedCol.add(col);
            dfs(n, row + 1, visitedCol, res);
            // 回溯
            visitedCol.remove(visitedCol.size() - 1);
        }
    }

    public boolean isDialog(List<Integer> visitedCol, int row, int col) {
        for (int i = 0; i < visitedCol.size(); i++) {
            int shifting = row - i;
            // 左右对角线
            if (visitedCol.get(i) == col - shifting || visitedCol.get(i) == col + shifting) {
                return true;
            }
        }
        return false;
    }

    public List<String> fillSonRes(List<Integer> visitedCol, int n) {
        List<String> sonRes = new ArrayList<>(n);
        for (int row = 0; row < visitedCol.size(); row++) {
            StringBuilder sb = new StringBuilder();
            for (int col = 0; col < n; col++) {
                if (col == visitedCol.get(row)) {
                    sb.append("Q");
                } else {
                    sb.append(".");
                }
            }
            sonRes.add(sb.toString());
        }
        return sonRes;
    }
}