算法——n皇后问题

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
链接: leetcode.

解题思路：

这是一道非常经典的dfs问题，只需要从头依次枚举各个情况即可。
这样设计dfs方式，先依次枚举每一行，在每一行中，再枚举当前行的每一个元素，每次枚举完一行，就继续向下一行枚举。
根据题目规则，设计枚举过程的冲突数组，防止皇后之间相互攻击。而冲突数组需要进行回溯。
下面的代码中，只有列、和两个斜向冲三个冲突组，这是为什么？因为我的枚举方式是以行为单位，所以，行是不可能冲突的。
两个斜向矛盾判断就是根据斜率的计算方法，将棋盘上的二维点映射到y轴。而斜率为负一的算式中，可能会使得数组的索引为负数，所以，为了方式这种情况，需要再计算y轴坐标的时候，统一加n。

class Solution {

    List<List<String>> res = new ArrayList<>();

    // 冲突数组

    boolean[] col, d, ud;

    int num;

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

        col = new boolean[n];

        d = new boolean[2 * n];

        ud = new boolean[2 * n];

        num = n;

		// 一层的原始状态字符串

        StringBuilder layer = new StringBuilder();

        // 一种方案

        List<String> plan = new ArrayList<>();

		// 初始化层的原始值

        for(int i = 0; i < n; i++) {

            layer.append(".");

        }

        dfs(0, layer, plan);

        return res;

    }

	// cur：当前的层号

	// layer：层的原始值

	// plan：遍历到当前层的已定方案

    public void dfs(int cur, StringBuilder layer, List<String> plan) {

        if(num == cur) {

        	// 当遍历完最后一层，说明已经形成了一种方案，不需要再遍历下去。

            res.add(new ArrayList<>(plan));

            return;

        }

		// 枚举当前层

        for(int i = 0; i < num; i++) {

        	// 判断当前位置是不是已经被占用了

            if(!col[i] && !d[cur + i] && !ud[cur - i + num]) {

            	// 占用当前位置

                col[i] = true;

                d[cur + i] = true;

                ud[cur - i + num] = true;

                layer.setCharAt(i, 'Q');

                plan.add(layer.toString());

                layer.setCharAt(i, '.');

				// 继续枚举下一层

                dfs(cur + 1, layer, plan);

				// 回溯

                plan.remove(plan.size() - 1);

                col[i] = false;

                d[cur + i] = false;

                ud[cur - i + num] = false;

            }

        }

    }

}

巴特西

算法——n皇后问题

最新文章

热门文章