8皇后问题的回溯算法实现

8皇后问题是一个经典的计算机科学问题，目标是在一个8x8的棋盘上放置8个皇后，使得任意两个皇后都不在同一行、同一列，以及斜线上。回溯算法是一种搜索策略，用于解决这类约束优化问题。

以下是基本的回溯算法实现步骤：

1. **初始化**：创建一个空数组表示棋盘，每个元素初始设为0，代表它还没有皇后。

2. **递归函数**：
- `isSafe(row, col)`：检查在给定行`row`和列`col`是否可以安全放置皇后，即该位置及其所在对角线范围内是否有其他皇后。
- `backtrack()`：回溯函数，尝试在每一行放皇后，并检查是否满足条件。如果当前行结束仍无解，则返回上一行继续尝试；如果有解，则将结果存储并回溯到前一行。

def backtrack(board):
    n = len(board)
    
    def isSafe(row, col):
        # 检查列、同行及左对角线和右对角线是否有皇后
        for i in range(col):
            if board[i] == row or \
               abs(board[i] - row) == col - i or \
               abs(board[i] - row) == i + col:
                return False
        return True
    
    if row >= n:
        # 如果所有皇后都已放置，找到了一个解决方案
        solutions.append(board.copy())
    else:
        for col in range(n):
            # 尝试在每列放置皇后
            if isSafe(row, col):
                board[row] = col
                # 继续下一行
                backtrack(board)
                # 当前行无解，回溯到上一行
                board[row] = -1

# 调用函数开始寻找解
board = [-1] * 8
solutions = []
backtrack(board)