N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：

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

示例 2：
输入：n = 1
输出：[["Q"]]

采用回溯算法解决 N 皇后问题，核心逻辑是 “逐行放置皇后，每行仅放一个，放置前检查位置合法性，合法则继续下一行，不合法则回溯（撤销当前放置）”，最终收集所有合法的棋盘布局。

思路：
1、合法性检查（check 函数）
检查规则：N 皇后的冲突条件是 “同一列、同一左对角线、同一右对角线”（无需检查行，因为逐行放置，每行仅放一个）：

列检查：遍历当前行以上的所有行，查看同一列（col）是否已有皇后，有则冲突；
左对角线检查：从当前位置向左上方（行 - 1、列 - 1）遍历，查看左对角线上是否已有皇后，有则冲突；
右对角线检查：从当前位置向右上方（行 - 1、列 + 1）遍历，查看右对角线上是否已有皇后，有则冲突；
若以上都无冲突，返回 “合法”，否则返回 “非法”。

2、回溯核心逻辑（backtracking 函数）
核心作用：递归逐行放置皇后，收集所有合法布局。

终止条件：当处理到第 n 行（row == n），说明前 n 行已合法放置所有皇后，此时将当前棋盘布局复制并保存到结果数组中；
逐列尝试：对当前行的每一列（j 从 0 到 n-1）执行以下操作：
检查当前位置 (row, j) 是否合法（调用 check 函数）；
若合法：在该位置放置皇后（赋值为 'Q'）；
递归处理下一行（row+1），继续尝试放置皇后；
回溯：递归返回后，撤销当前位置的皇后（赋值为 '.'），继续尝试当前行的下一列。

3、初始化与结果整理（solveNQueens 函数）
核心作用：初始化棋盘和结果容器，触发回溯，最终整理结果格式并返回。

初始化：
重置结果数量 returnSize 为 0；
分配结果数组（ans）和棋盘数组（board）的内存，棋盘初始化为全 '.'（空位置）；
触发回溯：从第 0 行开始调用回溯函数，逐行尝试放置皇后；
结果整理：
为每个合法布局分配列数数组（returnColumnSizes），标记每个布局的列数为 n；
返回最终收集的所有合法棋盘布局。

bool check(char** board, int row, int col, int n){
    for(int i = 0; i < row; i++){
        if(board[i][col] == 'Q') return false;
    }
    for(int i = row - 1, j = col - 1; i >= 0 && j >=0; i--, j--){
        if(board[i][j] == 'Q') return false;
    }
    for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++){
        if(board[i][j] == 'Q') return false;
    }
    return true;
}

void backtracking(char*** ans, char** board, int n, int* returnSize, int row){
    if(row == n){
        char** tmp = malloc(sizeof(char*) * (n + 1));
        for(int i = 0; i < n; i++){
            tmp[i] = malloc(sizeof(char) * (n + 1));
            tmp[i][n] = '\0';
            strcpy(tmp[i], board[i]);
        }
        ans[(*returnSize)++] = tmp;
    }
    for(int j = 0; j < n; j++){
        if(check(board, row, j, n)){
            board[row][j] = 'Q';
            backtracking(ans, board, n, returnSize, row + 1);
            board[row][j] = '.';
        }
    }
}

char*** solveNQueens(int n, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    char*** ans = malloc(sizeof(char**) * 501);
    char** board = malloc(sizeof(char*) * (n + 1));
    for(int i = 0; i < n; i++){
        board[i] = malloc(sizeof(char) * (n + 1));
        memset(board[i], '.', sizeof(char) * n);
        board[i][n]='\0';
    }
    backtracking(ans, board, n, returnSize, 0);
    *returnColumnSizes = malloc(sizeof(int) * (*returnSize));
    for(int i = 0; i < (*returnSize); i++){
        (*returnColumnSizes)[i] = n;
    }
    return ans;
}