算法笔记-N皇后求解

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;
   }