回溯法实现8皇后问题python

以下是一个python实现回溯法解决8皇后问题的示例代码：

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

def backtrack(board, row, result):
    if row == len(board):
        result.append(list(board))
        return
    for col in range(len(board)):
        if is_valid(board, row, col):
            # 做选择
            board[row][col] = 'Q'
            # 进入下一层决策树
            backtrack(board, row + 1, result)
            # 撤销选择
            board[row][col] = '.'

def solve_n_queens(n):
    board = [['.' for i in range(n)] for j in range(n)]
    result = []
    backtrack(board, 0, result)
    return result

解释：

- `is_valid` 函数用于检查在当前位置放置皇后是否合法。
- `backtrack` 函数用于递归地搜索所有可能的解。
- `solve_n_queens` 函数用于初始化棋盘并调用 `backtrack` 函数搜索所有解，最终返回所有解的列表。