52. N 皇后 II【 力扣(LeetCode) 】

零、原题链接

52. N 皇后 II

一、题目描述

  n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。【补充：不能互相攻击就是要求一个皇后的同行、同列、同斜线都不能存在其他皇后】

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

二、测试用例

示例 1：

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

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 9

三、解题思路

1. 基本思路：
     回溯+剪枝
2. 具体思路：
   • 每一行必定唯一存在一个皇后，所以确定皇后位置只要同一行确定即可【剪枝】
   • 每行尝试放置皇后，放置成功则将同列，同斜线的值++【因为是一行一行来放置皇后，所以可以设置值时可以不用设置当前行上面的】
   • 如果放置失败，则恢复状态；

四、参考代码

时间复杂度：$\mathrm{O}(n!)$
空间复杂度：$\mathrm{O}(n)$【递归栈的深度最高为 n】

class Solution {
public:vector<vector<int>> board = vector<vector<int>>(10, vector<int>(10, 0));int ans = 0, n;void Set(const int& x, const int& y, const int& num) {for (int i = x + 1; i < n; i++) {board[i][y] += num;}auto nx = x, ny = y;while (nx < n && ny < n) {board[nx++][ny++] += num;}nx = x, ny = y;while (nx < n && 0 <= ny) {board[nx++][ny--] += num;}}void dfs(const int& k) {if (k == n) {ans++;return;}for (int i = 0; i < n; i++) {if (board[k][i] == 0) {Set(k, i, 1);dfs(k + 1);Set(k, i, -1);}}}int totalNQueens(int n) {this->n = n;dfs(0);return ans;}
};