【LeetCode】N 皇后 II

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

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

示例 1：

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

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 9

#include <stdio.h>
#include <stdlib.h>

// 检查当前位置 (row, col) 是否可以放置皇后
int isSafe(int *queens, int row, int col, int n) {
    for (int i = 0; i < row; i++) {
        // 检查同列或同一对角线上是否有皇后
        if (queens[i] == col || abs(queens[i] - col) == abs(i - row)) {
            return 0;
        }
    }
    return 1;
}

// 回溯函数，尝试放置皇后
void backtrack(int *queens, int row, int n, int *count) {
    if (row == n) {  // 当放置完 n 个皇后时，找到一种解决方案
        (*count)++;
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isSafe(queens, row, col, n)) {  // 检查当前位置是否安全
            queens[row] = col;  // 在当前行的该列放置皇后
            // 递归放置下一行的皇后
            backtrack(queens, row + 1, n, count);
        }
    }
}

int totalNQueens(int n) {
    int *queens = (int *)malloc(n * sizeof(int));  // 存储皇后所在的列
    int count = 0;
    backtrack(queens, 0, n, &count);
    free(queens);  // 释放内存
    return count;
}