N皇后问题

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型 the n
# @return int整型
#
class Solution:
    def isValid(self, row, col, dp, n):
        # 检查同一列是否有相同的
        for i in range(row):
            if dp[i][col] == "Q":
                return False
        # 判断45°角
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if dp[i][j] == "Q":
                return False
            i -= 1
            j -= 1
        # 判断135°角
        i, j = row - 1, col + 1
        while i >= 0 and j < n:
            if dp[i][j] == "Q":
                return False
            i -= 1
            j += 1
        return True

    def backtracking(self, n, row, dp):
        if row == n:
            self.res += 1
            return
        for col in range(n):
            if self.isValid(row, col, dp, n):
                dp[row][col] = "Q"
                self.backtracking(n, row + 1, dp)
                dp[row][col] = "."

    def Nqueen(self, n: int) -> int:
        # write code here
        self.res = 0
        dp = [["."] * n for _ in range(n)]
        self.backtracking(n, 0, dp)
        return self.res

class Solution:
    # 判断当前坐标能不能放Q
    def __isOk(self, i, j, coords):
        for (row, col) in coords:
            # 同一行
            if i == row:
                return False
            # 同一列
            if j == col:
                return False
            # 斜对角
            if i + j == row + col:
                return False
            if i - j == row - col:
                return False
        return True

    def __dfs(self, n:int, k:int, coords):
        if k == n:
            self.count += 1
            return 

        for i in range(n):
            if self.__isOk(k, i, coords):
                coords.append((k, i))
                self.__dfs(n, k+1, coords)
                # 恢复状态
                coords.pop()


    def Nqueen(self , n: int) -> int:
        # write code here
        self.count = 0
        # 定义一个2*n的数组用来记录所有放Q的坐标
        coords = []
        # 从第一层开始遍历
        self.__dfs(n, 0, coords)
        return self.count

from itertools import permutations
class Solution:
    def Nqueen(self , n: int) -> int: 
        return len([v for v in permutations(range(n)) 
                    if n == len(set(v[i]+i for i in range(n))) == len(set(v[i]-i for i in range(n)))])

class Solution:
    #判断皇后是否符合条件
    def isValid(self, pos: List[int], row:int, col:int):
        # row为当前要放置皇后的行，col当前要摆放皇后的位置
        # 遍历之前所有行，皇后的所在位置
        for i in range(row):
            #不能同行同列同一斜线
            # 不能同列：col == pos[i] 判断当前位置，与之前行位置的皇后是否在同一位置
            # 不能同对角线：abs(row - i) == abs(col - pos[i]) 判断当前位置是否与之前的皇后在同一对角线上
            if col == pos[i]&nbs***bsp;abs(row - i) == abs(col - pos[i]):
                return False
        return True
     
    #递归查找皇后种类
    def recursion(self, n:int, row:int, pos:List[int], res:int):
        #完成全部行都选择了位置
        if row == n:
            res += 1
            return int(res)
        # 每行遍历所有可能
        for i in range(n):
            #检查该位置是否符合条件
            if self.isValid(pos, row, i): 
                #加入位置
                pos[row] = i
                #递归继续查找
                res = self.recursion(n, row + 1, pos, res)
        return res
 
    def Nqueen(self , n: int) -> int:
        res = 0
        # pos[i],i为第几行，pos[i]表示第i行的皇后放的位置，pos[3] = 7 第4行的皇后在第7位置
        pos = [0] * n
        # 递归
        result = self.recursion(n, 0, pos, res)
        return result

class Solution:
    def is_vaild(self, row, col, pos):
        for i in range(row):
            if row == i or col == pos[i] or abs(row-i) == abs(col-pos[i]):
                return False
        return True

    def recursion(self, pos, res, row, n):
        if row == n:
            res += 1
            return res
        for i in range(n):
            if self.is_vaild(row, i, pos):
                pos[row] = i
                res = self.recursion(pos, res, row+1, n)
        return res

    def Nqueen(self , n: int) -> int:
        pos = [0] * n
        res = 0
        result = self.recursion(pos, res, 0, n)
        return result

DFS

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int整型 the n
# @return int整型
#
class Solution:
    def Nqueen(self , n: int) -> int:
        # write code here
        ret = [1, 0, 0]
        if n <= 3:
            return ret[n - 1]

        # book[i] = j 表示第 i 行的“皇后”放在了第 j 列
        book = [-1] * n

        def valid(i, j):
            """验证当前点 (i,j) 与所有已经放置的点 (i_,j_) 是否共列或共斜线"""
            for i_ in range(i):
                j_ = book[i_]
                # 如果共列或共斜线，因为 i_ < i，所以不会共行
                if j == j_ or abs(i - i_) == abs(j - j_):
                    return False
            return True

        def dfs(i):
            """深度优先遍历每一行"""
            if i == n:  # 找到一种摆法
                return 1

            ret = 0
            for j in range(n):  # 遍历第 i 行的每个点 (i, j)
                if valid(i, j):  # 验证当前点 (i, j) 是否能放
                    book[i] = j
                    ret += dfs(i + 1)
                    # book[i] = -1  # 这里不需要回溯，因为 valid 只会遍历 book[0:i-1]

            return ret

        return dfs(0)