用回溯法求解8-皇后问题代码

8-皇后问题是一个经典的回溯算法示例，目标是在一个8x8的棋盘上放置8个皇后，使得任意两个皇后都不在同一行、同一列，以及同一对角线上。以下是用Python实现的一个简单版本的回溯法代码：

def is_valid(board, row, col):
    # 检查同行是否有皇后
    for i in range(col):
        if board[row][i] == 1:
            return False

    # 检查同列是否有皇后
    for i, j in enumerate(board[:row]):
        if j[col] == 1:
            return False

    # 检查左上到右下的对角线是否有皇后
    start = max(0, row - col)
    end = min(len(board) - 1, row + col)
    for i, j in zip(range(start, end + 1), range(row, -1, -1)):
        if board[i][j] == 1:
            return False

    # 检查右上到左下的对角线是否有皇后
    start = max(0, len(board) - 1)
    end = min(len(board) - 1, row)
    for i, j in zip(range(start, end + 1), range(row, len(board))):
        if board[i][j] == 1:
            return False

    # 如果通过所有检查，说明当前位置可以放皇后
    return True


def solve_n_queens(n, board=range(n)):
    # 如果皇后位置已填满，找到解决方案
    if len(board) == n:
        print("Solution found:")
        for i in range(n):
            print(' '.join(['.' if j != i else 'Q' for j in range(n)]))
        return

    # 遍历每一行，尝试放置皇后
    for col in range(n):
        if is_valid(board, len(board), col):
            board.append(col)  # 将皇后放在当前列
            solve_n_queens(n, board)  # 继续寻找下一个皇后的位置
            board.pop()  # 回溯：如果失败了，撤销这个选择并继续下一个位置


# 解决8皇后问题
solve_n_queens(8)