N-Queens Problem

N-Queens

在每步遍历搜索中，都要判断当前格子是否有效，在 dfs + backtracking 的结构不变的情况下，如何更快的判断就成为了程序的瓶颈。 一个比较好的方式是，利用一个皇后会占用这个格子的所有行，列以及对角线的特点，维护所有“行，列，45度对角线，135度对角线” 的 boolean array ，这样在每次考虑一个新位置的时候，只需要 O(1) 的时间进行一次操作就可以了。 boolean[ ] 可以，Java 的 BitSet 也不错，两者之间的比较：Boolean[ ] vs. BitSet: Which is more efficient?

45度对角线（左上到右下）的 row + colum 值是恒等的（一加一减），并且每条对角线的 row + column 值唯一, 在 [0,1,2 ... 2n - 2] 区间

135度对角线（左下到右上）的 row - column 值是恒等的（同加同减），并且每条对角线的 row - column 值唯一，在[-（n-1） ... -2,-1,0, 1, 2 ... n - 1 ] 区间

边长为 n 的棋盘，有 4n-2 条对角线，并且中间值 (0,0) 的 index 为 n - 1

N-Queens II

DFS + backtracking. 既然不需要输出最终解，也就省去了前者需要传递 res 和把棋盘转成 String 的过程。 但问题是如何在这种dfs + backtracking中返回有效解？ 求解的数量时，可以让 dfs 函数直接返回 int，每次迭代的时候将接下来迭代的返回结果加起来即可。