C++实现LeetCode(52.N皇后问题之二)

[LeetCode] 52. N-Queens II N皇后问题之二

The n-queens puzzle is the problem of placing nqueens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example:

Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
[".Q..",  // Solution 1
"...Q",
"Q...",
"..Q."],

 ["..Q.",  // Solution 2
"Q...",
"...Q",
".Q.."]
]

这道题是之前那道 N-Queens 的延伸，说是延伸其实我觉得两者顺序应该颠倒一样，上一道题比这道题还要稍稍复杂一些，两者本质上没有啥区别，都是要用回溯法 Backtracking 来解，如果理解了之前那道题的思路，此题只要做很小的改动即可，不再需要求出具体的皇后的摆法，只需要每次生成一种解法时，计数器加一即可，代码如下：

解法一：

 class Solution { public: int totalNQueens(int n) { int res = 0; vector pos(n, -1); helper(pos, 0, res); return res; } void helper(vector& pos, int row, int& res) { int n = pos.size(); if (row == n) ++res; for (int col = 0; col & pos, int row, int col) { for (int i = 0; i 

但是其实我们并不需要知道每一行皇后的具体位置，而只需要知道会不会产生冲突即可。对于每行要新加的位置，需要看跟之前的列，对角线，及逆对角线之间是否有冲突，所以我们需要三个布尔型数组，分别来记录之前的列 cols，对角线 diag，及逆对角线 anti_diag 上的位置，其中 cols 初始化大小为n，diag 和 anti_diag 均为 2n。列比较简单，是哪列就直接去 cols 中查找，而对角线的话，需要处理一下，如果我们仔细观察数组位置坐标的话，可以发现所有同一条主对角线的数，其纵坐标减去横坐标再加n，一定是相等的。同理，同一条逆对角线上的数字，其横纵坐标之和一定是相等的，根据这个，就可以快速判断主逆对角线上是否有冲突。任意一个有冲突的话，直接跳过当前位置，否则对于新位置，三个数组中对应位置都赋值为 true，然后对下一行调用递归，递归返回后记得还要还原状态，参见代码如下：

解法二：

 class Solution { public: int totalNQueens(int n) { int res = 0; vector cols(n), diag(2 * n), anti_diag(2 * n); helper(n, 0, cols, diag, anti_diag, res); return res; } void helper(int n, int row, vector& cols, vector& diag, vector& anti_diag, int& res) { if (row == n) ++res; for (int col = 0; col