用回溯算法求解n皇后问题。用Python实现并举例说明

n皇后问题是指在n×n的棋盘上放置n个皇后，使得皇后彼此之间不能相互攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上。

回溯算法是一种经典的解决此类问题的算法。其基本思想是通过深度优先搜索策略，逐步构建可行解，如果发现当前搜索路径无法构建出解，则返回上一层继续搜索，直到找到可行解或者搜索完所有可能的情况。

下面是Python实现n皇后问题的回溯算法，并且以n=4为例进行说明：

def is_valid(board, row, col, n):
    # 判断当前位置是否可以放置皇后
    # 检查当前列是否有皇后
    for i in range(row):
        if board[i][col] == 1:
            return False
    # 检查左上方是否有皇后
    i, j = row-1, col-1
    while i >= 0 and j >= 0:
        if board[i][j] == 1:
            return False
        i -= 1
        j -= 1
    # 检查右上方是否有皇后
    i, j = row-1, col+1
    while i >= 0 and j < n:
        if board[i][j] == 1:
            return False
        i -= 1
        j += 1
    return True

def backtracking(board, row, n, res):
    if row == n: # 已经找到一组解
        res.append([''.join(['Q' if i==1 else '.' for i in row]) for row in board])
        return
    for col in range(n): # 尝试在当前行的每个位置放置皇后
        if is_valid(board, row, col, n):
            board[row][col] = 1 # 放置皇后
            backtracking(board, row+1, n, res) # 继续搜索下一行
            board[row][col] = 0 # 回溯，撤销皇后
    return

def solveNQueens(n):
    res = []
    board = [[0] * n for i in range(n)]
    backtracking(board, 0, n, res)
    return res

print(solveNQueens(4))

输出结果为：

[['..Q.', 'Q...', '...Q', '.Q..'], ['.Q..', '...Q', 'Q...', '..Q.']]

其中，每个元素表示一组解，每行字符串表示棋盘上的一行，Q表示皇后，.表示空位。可以看到，对于n=4的情况，共有两组解。

具体实现中，is_valid函数用于判断当前位置是否可以放置皇后，backtracking函数则用于递归搜索所有可能的解。在backtracking函数中，首先判断是否已经找到一组解，如果已经找到，则将其加入结果集；如果没有找到，则在当前行的每个位置尝试放置皇后，并继续搜索下一行。如果当前搜索路径无法构建出解，则回溯并撤销当前放置的皇后，返回上一层继续搜索。