N皇后问题

转载请注明出处：https://www.jianshu.com/u/b03dcb8185b5

题目链接
题目：n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。（输入输出：给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。）

输入输出实例：
input：4
output：
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]

代码排版这么优美，注释如此详细，还有啥看不懂，欢迎评论区讨论

//参考代码如下
class Solution {
    private int n;
    private boolean[] col;//记录某一列是否放置了皇后
    private boolean[] main;//记录主对角线上的某一格是否放置了皇后
    private boolean[] sub;//记录副对角线上的某一格是否放置了皇后
    private List<List<String>> res;
    
    public List<List<String>> solveNQueens(int n) {
        res = new ArrayList<>();
        if(n == 0){
            return res;
        }
        //设置成员变量，减少参数传递
        this.n = n;
        this.col = new boolean[n];
        this.main = new boolean[2*n-1];
        this.sub = new boolean[2*n-1];
        Deque<Integer> path = new ArrayDeque<>();
        dfs(0, path);
        return res;
    }

    public void dfs(int row, Deque<Integer> path){
        if(row == n){
            //深搜到下标为n，表示[0,n-1]已经填完了，得到一个结果
            List<String> graph = convertGraph(path);
            res.add(graph);
            return;
        }
        //对于下标为row的每一列，尝试是否可以放置
        for(int i = 0; i < n; i++){
            if(!col[i] && !main[row+i] && !sub[row-i+n-1]){
                path.addLast(i);
                col[i] = true;
                main[row+i] = true;
                sub[row-i+n-1] = true;

                dfs(row+1, path);

                //递归完成后，回到之前的起点，需要将递归之前的操作恢复
                col[i] = false;
                main[row+i] = false;
                sub[row-i+n-1] = false;
                path.removeLast();
            }
        }
    }

    public List<String> convertGraph(Deque<Integer> path){
        List<String> graph = new ArrayList<>();
        for(Integer i : path){
            StringBuilder row = new StringBuilder();
            row.append(".".repeat(n));
            row.replace(i, i+1, "Q");
            graph.add(row.toString());
        }
        return graph;
    }
}

再来一道相似题

题目链接
题目：n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。（给定一个整数 n，返回 n 皇后不同的解决方案的数量。）

与上面一题的区别在于不记录每一种具体情况

输入输出示例：
input: 4
output: 2
解释: 4 皇后问题存在如下两个不同的解法。
[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]

//参考代码如下
class Solution {

    private boolean col[];
    private boolean main[];
    private boolean sub[];

    public int totalNQueens(int n) {
        col = new boolean [n];
        main = new boolean [2*n - 1];
        sub = new boolean [2*n - 1];
        return getResult(n, 0);
    }

    private int getResult(int n, int row){
        int res = 0;
        if(row == n){
            return 1;
        }

        for(int i = 0; i < n; i++){
            if(!col[i] && !main[row+i] && !sub[row-i+n-1]){
                //path.addLast(i);
                col[i] = true;
                main[row+i] = true;
                sub[row-i+n-1] = true;

                res += getResult(n, row+1);

                //递归完成后，回到之前的起点，需要将递归之前的操作恢复
                col[i] = false;
                main[row+i] = false;
                sub[row-i+n-1] = false;
                //path.removeLast();
            }
        }

        return res;
    }
}