python 回溯法 n皇后

回溯法是一种常用的解决问题的算法，它通常用于在搜索问题的所有解时使用。而 N 皇后问题是回溯算法中比较经典的问题之一，是指在一个 N × N 的棋盘上要摆 N 个皇后，使得任意两个皇后都不能处于同一行、同一列或同一斜线上。下面是 Python 中实现 N 皇后问题的回溯算法：

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def DFS(queens, xy_dif, xy_sum):
            p = len(queens)
            if p==n:
                result.append(queens)
                return None
            for q in range(n):
                if q not in queens and p-q not in xy_dif and p+q not in xy_sum:
                    DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])  

        result = []
        DFS([],[],[])
        return [["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]

相关问题

回溯法n皇后问题python

以下是回溯法解决n皇后问题的Python代码实现：

n = 4
res = [-1 for i in range(n)]

def isRight(curr:int):
    for i in range(curr+1):
        for j in range(i+1,curr+1):
            if i==j or res[i]==res[j] or abs(i-j)==abs(res[i]-res[j]):
                return False
    return True

def NQueen(curr:int):
    if curr < n:
        for i in range(n):
            res[curr] = i
            if isRight(curr):
                NQueen(curr+1)
            else:
                res[curr] = -1
    else:
        print(res)

NQueen(0)

该代码使用了递归和回溯的思想，首先定义了一个长度为n的数组res，用于存储每个皇后所在的列数。然后定义了一个isRight函数，用于判断当前放置的皇后是否与之前的皇后产生冲突。最后定义了一个NQueen函数，用于递归地放置皇后。在NQueen函数中，首先判断当前行是否已经放置完毕，如果没有，则依次尝试每一列，如果当前列可以放置，则继续递归下一行；否则回溯到上一行，继续尝试下一列。当第一行的皇后放置完毕后，即可输出结果。

n皇后python回溯法

下面是一个基于回溯法的 n 皇后 Python 实现：

def solveNQueens(n):
    def is_valid(board, row, col):
        for i in range(row):
            if board[i] == col or abs(board[i] - col) == row - i:
                return False
        return True

    def backtrack(board, row):
        if row == n:
            res.append(list(board))
            return
        for col in range(n):
            if is_valid(board, row, col):
                board[row] = col
                backtrack(board, row + 1)
                board[row] = -1

    res = []
    board = [-1] * n
    backtrack(board, 0)
    return res

这里采用一个一维数组 `board` 来表示棋盘，`board[i]` 表示第 i 行皇后所在的列数，初始值为 -1。在每一行中，我们枚举该行所有列，如果可以放置皇后，则将其放置在该位置，并递归处理下一行。如果发现该位置无法放置皇后，则回溯到上一行重新处理。

`is_valid()` 函数用于判断当前位置是否可以放置皇后。若在同一列或同一对角线上已经有皇后，则返回 False。如果没有冲突，则返回 True。

最终返回的是所有可行的皇后摆法，每一种摆法都表示为一个长度为 n 的列表，列表的第 i 个元素表示第 i 行皇后所在的列数。