51.N皇后

链接：51.N皇后
难度：Hard
标签：数组、回溯
简介：n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

题解 1 - typescript

• 编辑时间：2021-07-25
• 执行用时：108ms
• 内存消耗：44.7MB
• 编程语言：typescript
• 解法介绍：dfs+剪枝。

function solveNQueens(n: number): string[][] {
  const ans: string[][] = [];
  const colSet = new Set<number>();
  const lineSet = new Set<string>();
  const board = new Array(n).fill(0).map(_ => new Array(n).fill('.'));
  dfs();
  return ans;
  function getLine(row: number, col: number): [string, string] {
    return [`y=x+${n - 1 - row - col}${specStr}, ${specStr}y=-x+${n - 1 - row + col}`];
  }
  function dfs(row: number = 0) {
    if (row === n) {
      const newBoard: string[] = new Array(n).fill(0).map((_, row) =>
        new Array(n)
          .fill(0)
          .map((_, col) => board[row][col])
          .join('')
      );
      ans.push(newBoard);
      return;
    }
    for (let col = 0; col < n; col++) {
      if (colSet.has(col)) continue;
      const [line1, line2] = getLine(row, col);
      if (lineSet.has(line1) || lineSet.has(line2)) continue;
      colSet.add(col);
      lineSet.add(line1);
      lineSet.add(line2);
      board[row][col] = 'Q';
      dfs(row + 1);
      board[row][col] = '.';
      colSet.delete(col);
      lineSet.delete(line1);
      lineSet.delete(line2);
    }
  }
}

题解 2 - python

• 编辑时间：2024-12-01
• 执行用时：1707ms
• 内存消耗：17.51MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        rows, cols, k1, k2 = [False] * n, [False] * n, [False] * (n * 3), [False] * (n * 3)
        tok1 = lambda i, j: n - i - j
        tok2 = lambda i, j: n - i + j
        res, data = [], [['.'] * n for _ in range(n)]
        def dfs(i: int, j: int, cnt: int):
            nonlocal res
            if i == n:
                if cnt == 0:
                    item = []
                    res.append(item)
                    for row in data: item.append(''.join(row))
                return
            if j == n:
                dfs(i + 1, 0, cnt)
                return
            dfs(i, j + 1, cnt)
            if not rows[i] and not cols[j] and not k1[tok1(i, j)] and not k2[tok2(i, j)]:
                rows[i] = cols[j] = k1[tok1(i, j)] = k2[tok2(i, j)] = True
                data[i][j] = 'Q'
                dfs(i, j + 1, cnt - 1)
                data[i][j] = '.'
                rows[i] = cols[j] = k1[tok1(i, j)] = k2[tok2(i, j)] = False
        dfs(0, 0, n)
        return res

题解 3 - javascript

• 编辑时间：2020-04-27
• 执行用时：72ms
• 内存消耗：36.1MB
• 编程语言：javascript
• 解法介绍：回溯算法，遍历后剪枝。

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
  const cols = new Array(n);
  const res = [];
  queues(0);
  function queues(row) {
    if (row === n) {
      res.push(getRes());
    }
    for (let col = 0; col < n; col++) {
      if (isValid(row, col)) {
        cols[row] = col;
        queues(row + 1);
      }
    }
  }
  function isValid(row, col) {
    for (let i = 0; i < row; i++) {
      if (cols[i] === col) return false;
      if (row - i === Math.abs(cols[i] - col)) return false;
    }
    return true;
  }
  function getRes() {
    const res = [];
    for (let row = 0; row < n; row++) {
      let string = '';
      for (let col = 0; col < n; col++) {
        if (cols[row] === col) string += 'Q';
        else string += '.';
      }
      res.push(string);
    }
    return res;
  }
  return res;
};