【Day 49 】2024-05-26 - 52. N 皇后 II

[azl397985856]

52. N 皇后 II

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/n-queens-ii/

前置知识

• 回溯
• 深度优先遍历

  题目描述

  
  n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

示例 1：

![](https://p.ipic.vip/e9jfjh.jpg)

输入：n = 4 输出：2 解释：如上图所示，4 皇后问题存在两个不同的解法。 示例 2：

输入：n = 1 输出：1  

提示：

1 <= n <= 9 皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。

[Hermione666]

class Solution: def totalNQueens(self, n: int) -> int: ans = 0

Initialize the markers for columns and diagonals

    on_path = [False] * n
    diag1 = [False] * (2 * n - 1)
    diag2 = [False] * (2 * n - 1)

    def dfs(r):
        nonlocal ans
        if r == n:
            ans += 1
            return

        for c in range(n):
            # Calculate the indices for the diagonals
            d1 = r + c
            d2 = r - c + n - 1

            # Check if the column and diagonals are not attacked
            if not on_path[c] and not diag1[d1] and not diag2[d2]:
                # Place the queen
                on_path[c] = diag1[d1] = diag2[d2] = True
                # Move to the next row
                dfs(r + 1)
                # Remove the queen and restore the state
                on_path[c] = diag1[d1] = diag2[d2] = False

    dfs(0)
    return ans

[lxy1108]

python3 代码

class Solution:
    def totalNQueens(self, n: int) -> int:
        def check(inaval,count,idxstart):
            rs = 0
            if count==n:
                return 1
            if len(inaval)==n**2:
                return 0
            istart = idxstart//n
            jstart = idxstart%n
            for idx in range(idxstart,n**2):
                i,j = idx//n,idx%n
                if (i,j) not in inaval:
                    inaval_tmp = inaval.copy()
                    inaval_tmp.add((i,j))
                    for k in range(n):
                        if (i,k) not in inaval_tmp:
                            inaval_tmp.add((i,k))
                        if (k,j) not in inaval_tmp:
                            inaval_tmp.add((k,j))
                        if i+j-k>=0 and i+j-k<n and (k,i+j-k) not in inaval_tmp:
                            inaval_tmp.add((k,i+j-k))
                        if k-i+j>=0 and k-i+j<n and (k,k-i+j) not in inaval_tmp:
                            inaval_tmp.add((k,k-i+j))
                    # print(i,j,inaval_tmp,count)
                    rs += check(inaval_tmp,count+1,i*n+j+1)
            return rs
        return check(set(),0,0)

[xy147]

js代码

var totalNQueens = function (n) {
  let res = 0;
  const dfs = (n, row, col, pie, na) => {
    if (row >= n) {
      res++;
      return;
    }
    let bits = ~(col | pie | na) & ((1 << n) - 1);
    while (bits) {
      let p = bits & -bits;
      bits = bits & (bits - 1);
      dfs(n, row + 1, col | p, (pie | p) << 1, (na | p) >> 1);
    }
  };
  dfs(n, 0, 0, 0, 0);
  return res;
};

复杂度分析

时间复杂度：O(n!) 空间复杂度：O(n)

[franklinsworld666]

代码

class Solution:
    def totalNQueens(self, n: int) -> int:
        def can_place(row):
            # 检查当前行放置皇后是否安全
            for i in range(row):
                if col[i] == col[row] or \
                   abs(col[i] - col[row]) == row - i:
                    return False
            return True

        def backtrack(row):
            if row == n:
                result.append(generate_board())
                return
            for i in range(n):
                col[row] = i
                if can_place(row):
                    backtrack(row + 1)

        def generate_board():
            # 生成当前解决方案的棋盘表示
            board = [["." for _ in range(n)] for _ in range(n)]
            for i in range(n):
                board[i][col[i]] = "Q"
            return board

        col = [-1] * n  
        result = []  
        backtrack(0)  
        return len(result)