2.回溯法求解N后问题Python

回溯法是一种经典的搜索算法，用于解决那些存在大量可能解决方案的问题，比如找零钱、八皇后问题等。在Python中，我们可以利用递归的方式来实现回溯法求解N皇后问题（即在一个N×N的棋盘上放置N个皇后，保证任意两个皇后都不在同一行、同一列或对角线上）。以下是基本的步骤：

1. 定义一个函数`solveNQueens`，接收棋盘的大小`n`作为参数。
2. 创建一个二维数组`board`表示棋盘，初始化所有元素为None，表示未放置皇后。
3. 函数开始递归，尝试将皇后放在第一行的第一个位置，然后检查是否违反了规则。
4. 如果可以放置，则继续递归在下一行寻找合适的放置位置；如果不满足条件（如冲突），则回溯到上一行，尝试下一个位置。
5. 当所有皇后都成功放置完时，返回True表示找到了一个解决方案。
6. 为了避免重复找到相同的解，需要记录已经访问过哪些位置，并在回溯时跳过它们。

def is_safe(board, row, col):
    # 检查行、列以及左上方对角线是否有冲突
    for i in range(row):
        if board[i] == col or board[i] - i == col - row or board[i] + i == col + row:
            return False
    return True

def solveNQueens(n):
    def place_queen(board, row):
        if row == n:
            # 找到一个解，打印出来并返回True
            print(board)
            return True
        for col in range(n):
            if is_safe(board, row, col):
                # 尝试放皇后
                board[row] = col
                if place_queen(board, row + 1):  # 递归向下一层
                    return True
                else:  # 回溯，移除皇后
                    board[row] = None
        return False

    board = [None] * n
    if not place_queen(board, 0):
        print("No solution found.")
    return

# 调用函数，传入你要解决的N皇后问题的大小
solveNQueens(8)