LC52.N皇后II

1. 题目

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

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

示例 1：

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

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 9

2. 思路

• 递归遍历每一行，需要三个辅助数组来判断是否重复：col/dg/rdg，其中，col 用来判定同一列是否存在重复元素，dg 用来判定对角线是否存在重复元素，rdg 用来表示逆向对角线是否存在重复元素
• 可以说，此题的真正难点，就在于如何判定重复，对于 col 而言，如果 col[c] == 1，那么就判定为重复，对于 dg而言，r+c 一定是定值，范围在 [0, 2n-2] 。对于 rdg，r-c 也是定值，范围在 [1-n,n-1]，因此，r-c+n 范围在 [1, 2*n - 1] 区间当中。

3. 代码

func totalNQueens(n int) (ans int) {
	col := make([]int, n)
	dg := make([]int, 2*n)
	rdg := make([]int, 2*n)

	var dfs func(r int)

	dfs = func(r int) {
		if r == n-1 {
			ans += 1
			return
		}

		for c := 0; c < n; c++ {
			if col[c] == 1 || dg[c+r] == 1 || rdg[c-r+n] == 1 {
				continue
			}

			col[c], dg[c+r], rdg[c-r+n] = 1, 1, 1
			dfs(r + 1)
			col[c], dg[c+r], rdg[c-r+n] = 0, 0, 0
		}
	}

	dfs(0)
	return ans
}