n皇后问题的回溯算法python

以下是n皇后问题的回溯算法Python实现：

def solveNQueens(n):
    def DFS(queens, xy_dif, xy_sum):
        nonlocal count
        p = len(queens)
        if p == n:
            count += 1
            return
        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])  
    count = 0
    DFS([],[],[])
    return count

n = 8
print(f"{n}皇后问题有{solveNQueens(n)}种解法")

相关问题

8皇后问题回溯算法Python

8皇后问题是一个经典的问题，它的目标是在8x8的棋盘上放置8个皇后，使得每个皇后都不能互相攻击。回溯算法是一种常用的解决8皇后问题的方法。下面是Python代码实现：

class Solution:
    def __init__(self):
        self.res = []
        self.cols = set()
        self.pie = set()
        self.na = set()

    def solveNQueens(self, n: int) -> List[List[str]]:
        if n < 1:
            return []
        self._dfs(n, 0, [])
        return self.res

    def _dfs(self, n, row, cur_state):
        if row >= n:
            self.res.append(cur_state)
            return
        for col in range(n):
            if col in self.cols or row + col in self.pie or row - col in self.na:
                continue
            self.cols.add(col)
            self.pie.add(row + col)
            self.na.add(row - col)

            self._dfs(n, row + 1, cur_state + [col])

            self.cols.remove(col)
            self.pie.remove(row + col)
            self.na.remove(row - col)

在这段代码中，我们使用了一个递归函数 `_dfs`。对于每一行，我们尝试放置皇后在每一列中。如果当前位置不会与之前的皇后相互攻击，则将当前位置的列、撇和捺记录下来，然后递归到下一行。如果无法找到一个合法的位置，则回溯到上一行并且继续寻找其他的位置。

n皇后问题回溯法python代码实现，以及时间复杂度分析，空间复杂度分析

N皇后问题是指在N*N的棋盘上放置N个皇后，使得皇后之间不能互相攻击，即任意两个皇后都不能在同一行、同一列或同一斜线上。下面是N皇后问题的回溯法Python代码实现：

def is_valid(board, row, col):
    # 检查列是否有皇后互相冲突
    for i in range(row):
        if board[i] == col:
            return False
    # 检查右上方是否有皇后互相冲突
    i, j = row - 1, col + 1
    while i >= 0 and j < len(board):
        if board[i] == j:
            return False
        i, j = i - 1, j + 1
    # 检查左上方是否有皇后互相冲突
    i, j = row - 1, col - 1
    while i >= 0 and j >= 0:
        if board[i] == j:
            return False
        i, j = i - 1, j - 1
    return True


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


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

时间复杂度分析：该算法的时间复杂度是指数级别的，因为在每一行中，每个皇后都有N种可能的放置位置，因此总时间复杂度为O(N^N)。

空间复杂度分析：该算法的空间复杂度为O(N)，因为需要记录每个皇后的位置。