LeetCode_91_NQueens

1. question: N皇后（困难）

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/n-queens

示例 1：

输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

输入：n = 1
输出：[["Q"]]

提示：

1 <= n <= 9

2. answers

这道题是回溯法的经典问题。主要需要注意一下几点：

1. 棋盘的坐标问题。
2. 可以明确的是，每行肯定要放一个元素。这样递归的时候，同行就不需要判断了。
3. 同列，其实也很好判断。
4. 至于同斜线：前面行与下一行的行数差，再加上前面行所选的下标，就是下一行所不能选择的下标。

为了方便，

1. 棋盘下标为[0, n-1]
2. 可直接保存，前面行的所选下标。
3. 可直接保存，下一行的可选下标。

代码如下所示：

public class Solution_0091 {

    // 保存每一种结果
    LinkedList<String> group = new LinkedList<>();

    // 保存所有结果
    List<List<String>> result = new ArrayList<>();

    public void getRes(int n, List<Integer> remainSel, List<Integer> preSel) {

        // 终止递归
        if(preSel.size() == n) {
            result.add(new ArrayList<>(group));
            return;
        }

        // 有如下选择
        for(Integer i: remainSel) {

            // 生成当前行的结果。
            StringBuilder pre = new StringBuilder();
            for (int j = 0; j < i; j++) {
                pre.append(".");
            }

            StringBuilder post = new StringBuilder();
            for (int j = i; j < n - 1; j++) {
                post.append(".");
            }

            group.add(pre + "Q" + post);

            // 生成下一行的选择，注意不能当前行的选择同列，同一斜线。
            // 注意，还要保证和前面所有行的选择都不冲突
            List<Integer> remain = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                remain.add(j);
            }

            preSel.add(i);
            int size = preSel.size();   // 与当前行的差距
            for(Integer j: preSel) {
                remain.remove(j);
                if(j - size >= 0) remain.remove(Integer.valueOf(j-size));
                if(j + size < n) remain.remove( Integer.valueOf(j+size));
                size--;
            }

            // 递归下一行
            getRes(n, remain, preSel);

            // 回溯，注意要删除当前已经添加的preSel
            group.removeLast();
            preSel.remove(i);
        }
    }

    public List<List<String>> solveNQueens(int n) {

        List<Integer> remain = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            remain.add(i);
        }

        List<Integer> preSel = new ArrayList<>();

        getRes(n, remain, preSel);

        return result;
    }

    public static void main(String[] args) {


        Solution_0091 s = new Solution_0091();

//        List<List<String>> lists = s.solveNQueens(4);
        List<List<String>> lists = s.solveNQueens(1);

        for(List<String> list: lists) {

            for(String ss: list)
                System.out.print(ss + "\t");

            System.out.println();
        }
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。