LeetCode热题（JS版） – 51. N皇后

题目

给定一个整数 n，返回所有不同的 $n$ 皇后问题的解决方案。每个解决方案包含一个明确的 $n$ 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例:

输入: 4 输出: [ [“.Q..”, // 解法 1 “…Q”, “Q…”, “..Q.”],

[“..Q.”, // 解法 2 “Q…”, “…Q”, “.Q..”] ] 解释: 4 皇后问题存在两个不同的解法。

思路

这道题可以使用回溯算法来解决。从第一行开始，逐行遍历并在每个位置上放置 Q，判断是否满足条件。如果满足，则进入下一行继续放置 Q，否则回退到上一行重新放置。

具体地，我们定义一个二维 boolean 数组 board 来表示棋盘，其中 board[i][j] 表示第 i 行第 j 列是否被占用。对于每一行，我们先尝试在该行的每个位置放置 Q，判断该位置是否符合要求。如果符合要求，则更新 board 并进入下一行；否则回溯到上一行，并清除之前放置的 Q。

当放置 Q 的行数达到 $n$ 时，说明找到了一组解法，将其加入结果数组中。

实现

function solveNQueens(n: number): string[][] {
  const res: string[][] = [];
  const board: boolean[][] = Array.from({ length: n }, () =>
    new Array<boolean>(n).fill(false)
  );

  const backtrack = (row: number) => {
    if (row === n) {
      const solution: string[] = board.map((row) =>
        row.map((occupied) => (occupied ? "Q" : ".")).join("")
      );
      res.push(solution);
      return;
    }

    for (let col = 0; col < n; col++) {
      if (isValid(row, col, board)) {
        board[row][col] = true;
        backtrack(row + 1);
        board[row][col] = false;
      }
    }
  };

  const isValid = (
    row: number,
    col: number,
    board: boolean[][]
  ): boolean => {
    // 检查列是否有冲突
    for (let i = 0; i < row; i++) {
      if (board[i][col]) {
        return false;
      }
    }

    // 检查左上方是否有冲突
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j]) {
        return false;
      }
    }

    // 检查右上方是否有冲突
    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (board[i][j]) {
        return false;
      }
    }

    return true;
  };

  backtrack(0);
  return res;
}

时间复杂度

本题中，每行只能放置一个皇后，因此在回溯算法中，有 $n$ 行可以选择在哪里放置 Q。对于每一行，最多有 $n$ 种可能的放置位置。因此，总共的时间复杂度为 $O(n^n)$。

空间复杂度

空间复杂度的主要消耗来自于递归时占用的栈空间，其空间复杂度为 $O(n)$。除此之外，还需要使用一个二维 boolean 数组来表示棋盘，其空间复杂度也为 $O(n^2)$。因此，总共的空间复