n皇后問題是一個以國際象棋為背景的問題：在n×n的國際象棋棋盤上放置n個皇后，使得任何一個皇后都無法直接吃掉其他的皇后，即任意兩個皇后都不能處于同一條橫行、縱行或斜線上。請問有多少種擺法，并將每種擺法打印出來。

遞歸算法1（最暴力的解法）

可以從左到右嘗試棋子的擺放，例如先放置在第一行（1，1）放置，然后在第二行開始找與第一行放置不沖突的棋子，找到了（2，3），接著開始在第三行找，找到了（3，2）……一直到最后一行。如果出現下一行的每一列都有沖突，則返回到上一行，修改上一行的放置……重復上面的操作。

1. 關于存儲放置的棋子的坐標，一般會想到二維數組來存放，如arr[i][j]=1,代表i行，j列有棋子，實際上用一個一維數組就可以解決該問題。例如a[4]=1表示第4列有棋子，而且無需再判斷兩個皇后是否在同一行。
2. 關于如何判斷兩個棋子在不在對角線，若兩個棋子坐標（X ₁，Y₁），（X ₂，Y₂），則 |X ₁-X₂| != |Y ₁-Y₂|。當然在在之前應該首先判斷在不在同一列（a[j]==y）

   /* 回溯算法：n 皇后 */
   void backtrack(int row, int n, char state[MAX_SIZE][MAX_SIZE], char ***res, int *resSize, bool cols[MAX_SIZE],
   bool diags1[2 * MAX_SIZE - 1], bool diags2[2 * MAX_SIZE - 1]) {
   // 當放置完所有行時，記錄解
   if (row == n) {
   res[*resSize] = (char **)malloc(sizeof(char *) * n);
   for (int i = 0; i < n; ++i) {
   res[*resSize][i] = (char *)malloc(sizeof(char) * (n + 1));
   strcpy(res[*resSize][i], state[i]);
   }
   (*resSize)++;
   return;
   }
   // 遍歷所有列
   for (int col = 0; col < n; col++) {
   // 計算該格子對應的主對角線和次對角線
   int diag1 = row - col + n - 1;
   int diag2 = row + col;
   // 剪枝：不允許該格子所在列、主對角線、次對角線上存在皇后
   if (!cols[col] && !diags1[diag1] && !diags2[diag2]) {
   // 嘗試：將皇后放置在該格子
   state[row][col] = 'Q';
   cols[col] = diags1[diag1] = diags2[diag2] = true;
   // 放置下一行
   backtrack(row + 1, n, state, res, resSize, cols, diags1, diags2);
   // 回退：將該格子恢復為空位
   state[row][col] = '#';
   cols[col] = diags1[diag1] = diags2[diag2] = false;
   }
   }
   }

   /* 求解 n 皇后 */
   char ***nQueens(int n, int *returnSize) {
   char state[MAX_SIZE][MAX_SIZE];
   // 初始化 n*n 大小的棋盤，其中 'Q' 代表皇后，'#' 代表空位
   for (int i = 0; i < n; ++i) {
   for (int j = 0; j < n; ++j) {
   state[i][j] = '#';
   }
   state[i][n] = '\0';
   }
   bool cols[MAX_SIZE] = {false}; // 記錄列是否有皇后
   bool diags1[2 * MAX_SIZE - 1] = {false}; // 記錄主對角線上是否有皇后
   bool diags2[2 * MAX_SIZE - 1] = {false}; // 記錄次對角線上是否有皇后

   char ***res = (char ***)malloc(sizeof(char **) * MAX_SIZE);
   *returnSize = 0;
   backtrack(0, n, state, res, returnSize, cols, diags1, diags2);
   return res;
   }