力扣小白刷题之51题N皇后
题目描述
将 n 个皇后放置在 n * n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。 每一种解法包含一个明确的 n 皇后问题的棋子防止方案，该方案中 ‘Q’ 和 ‘.’ 分别代表皇后和空位。
分析
参考：https://leetcode-cn.com/problems/n-queens/solution/gen-ju-di-46-ti-quan-pai-lie-de-hui-su-suan-fa-si-/
以 四皇后 为例，给棋盘的每一行从左到右标记为：1、2、3、4。
决策树的每一层表示棋盘上的每一行，每个节点可以做出的选择是：在该行的任意一列放置一个皇后。
画出递归树如下图： 整体就是“全排列” 问题 + 剪枝，剪枝的依据就是 “N皇后” 问题的规则。
思路
皇后可以攻击上、下、左、右、左上、左下、右上、右下8个方向
-
因为是一行一行摆放，因此这些“皇后”一定不在同一行，无需额外设置状态； 为了保证不在同一列，需要设置 列标记数组 used[] 作为“状态”变量； 为了保证至少两个皇后不同时出现在主对角线或者副对角线，策略是：只要“检测”到新摆放的“皇后”与已经摆放好的“皇后”冲突，就尝试摆放下一个位置，在“无处安放”的时候“剪枝”。
研究一下主对角线(135°)和副对角线(45°)上的元素的特性，此时我们掌握的信息只有行和列的索引，将它们标在棋盘上。 归纳得出： 45 度（副）对角线标记数组的长度为 2 * n - 1，通过下图可以明确 (r, c) 的位置所在的数组下标为 r + c。 135 度（主）对角线标记数组的长度也是 2 * n - 1，(r, c) 的位置所在的数组下标为 n - 1 - (r - c)。
-
然后像used[]列标记数组一样，我们再为“主对角线”和“副对角线”设置相应的标记数组变量，只要排定一个“皇后”的位置，就相应地占住相应的位置。 因为位置有限，标记数组可以使用数组，但是数组的元素个数需要归纳得到。也可以使用哈希表表示“状态”。
具体步骤：
- 每行都要放置一个且只能放置一个皇后。
- 利用递归对棋盘每一行放置皇后，放置时，按列顺序寻找可以放置皇后的列，若可以放置皇后，将皇后放置该位置，并更新标记数组，递归进行下一行的皇后放置
- 当递归进行不下去的时候，恢复标记数组，回溯。
- 当递归完成N行的N个皇后放置，则将该结果保存并返回。
代码
一点问题
- Java数组的Arrays.fill()方法 用于一维数组、二维数组的初始化或填充 public static void fill(Object[] a, int fromIndex, int toIndex, Object val) 将指定的 Object 引用分配给指定 Object 数组指定范围中的每个元素。填充的范围从索引 fromIndex（包括）一直到索引 toIndex（不包括）。（如果 fromIndex==toIndex，则填充范围为空。） 参数： a - 要填充的数组 fromIndex - 要使用指定值填充的第一个元素的索引（包括） toIndex - 要使用指定值填充的最后一个元素的索引（不包括） val - 要存储在数组的所有元素中的值 例子：
- new String(char[] chars) String类中有能接受字符数组类型的构造方法，把字符数组转换成字符串 函数原型： public String (char [] value): 把字符数组转化为字符串 public String (char[] value,int index,int length):从字符数组的第index位将字符串的length个字节转化为字符串
