N 皇后II

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。给你一个整数 n ,返回 n 皇后问题 不同的解决方案的数量。

[card title="示例" color="info"]

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

示例2:
输入:n = 1
输出:1

题目详情[/card]

C++

class Solution {
public:
    int res = 0;
    int vis[3][20];
    int totalNQueens(int n) {
        memset(vis, 0, sizeof(vis));
        core(n, 0);
        return res;
    }

    void core(int n, int r) {
        if (r == n) {
            ++res;
        } else {
            for (int i = 0; i < n; ++i) {
                if (!vis[0][i] && !vis[1][r + i] && !vis[2][r - i + n]) {
                    vis[0][i] = vis[1][r + i] = vis[2][r - i + n] = 1;
                    core(n, r + 1);
                    vis[0][i] = vis[1][r + i] = vis[2][r - i + n] = 0;
                }
            }
        }
    }
};

回溯算法