52.N皇后II

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

题解 1 - typescript

• 编辑时间：2020-10-17
• 执行用时：96ms
• 内存消耗：40MB
• 编程语言：typescript
• 解法介绍：回溯。

function totalNQueens(n: number): number {
  const cols = new Array(n);
  let ans = 0;
  find(0);
  return ans;
  function find(row: number) {
    if (row === n) {
      ans++;
      return;
    }
    for (let i = 0; i < n; i++) {
      if (check(row, i)) {
        cols[row] = i;
        find(row + 1);
      }
    }
  }
  function check(row: number, col: number): boolean {
    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;
  }
}

题解 2 - javascript

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

/**
 * @param {number} n
 * @return {string[][]}
 */
var totalNQueens = function (n) {
  const cols = new Array(n);
  let res = 0;
  queues(0);
  function queues(row) {
    if (row === n) {
      res++;
    }
    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;
  }
  return res;
};

题解 3 - python

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

class Solution:
    def totalNQueens(self, n: int) -> int:
        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 = 0
        def dfs(i: int, j: int, cnt: int):
            nonlocal res
            if i == n:
                res += cnt == 0
                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
                dfs(i, j + 1, cnt - 1)
                rows[i] = cols[j] = k1[tok1(i, j)] = k2[tok2(i, j)] = False
        dfs(0, 0, n)
        return res