Leetcode52： N 皇后 II

题目描述：

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

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

代码思路：

这段代码是解决经典的N皇后问题的变种，通过递归和回溯的方式，旨在计算在一个N×N的棋盘上放置N个皇后，使得它们互不攻击（即任意两个皇后不能在同一行、同一列或同一对角线上）的所有可能摆放方式的总数。以下是代码的详细思路解析：

类和方法定义

• 类定义：class Solution 是定义问题的解决方案的类。
• 方法定义：
  • def totalNQueens(self, n: int) -> int：这是类 Solution 的主方法，用于初始化一些变量并调用递归方法 Queen 来计算并返回N皇后问题的解的总数。
  • def Queen(self, n, col, diag1, diag2)：这是一个递归方法，用于尝试在棋盘上放置皇后，并检查当前放置是否合法。如果合法，则继续放置下一个皇后；如果不合法，则尝试其他位置。

变量解释

• self.ans：用于存储所有合法的N皇后摆放方式的总数。
• self.target：存储棋盘的大小N，即要放置的皇后的数量。
• n：当前正在放置的皇后的编号（从0开始）。
• col：一个列表，存储每一列上是否有皇后（通过列索引表示）。
• diag1：一个列表，存储从左上到右下的对角线上是否有皇后（通过对角线编号表示，计算方式为 i-n）。
• diag2：一个列表，存储从右上到左下的对角线上是否有皇后（通过对角线编号表示，计算方式为 self.target - i - n）。

算法思路

代码实现：

class Solution:
    def totalNQueens(self, n: int) -> int:
        self.ans = 0
        self.target = n
        self.Queen(0, [], [], [])
        return self.ans

    def Queen(self, n, col, diag1, diag2):  #diag1为左上到左下，diag2为右上到右下
        if n == self.target:
            self.ans += 1
        else:
            for i in range(self.target):
                if (i not in col) and (i-n not in diag1) and (self.target - i - n not in diag2):
                    self.Queen(n + 1, col + [i], diag1 + [i-n], diag2 + [self.target - i - n])