回溯法求n皇后问题 python代码

下面是使用回溯法求解N皇后问题的Python代码：

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


def solve_n_queens(n):
    """
    解决N皇后问题
    """
    board = [[0] * n for _ in range(n)]
    res = []
    def backtrack(board, row):
        # 找到一个可行解
        if row == n:
            res.append(["".join(["Q" if c == 1 else "." for c in r]) for r in board])
            return
        for col in range(n):
            if is_valid(board, row, col):
                # 在当前位置放置皇后
                board[row][col] = 1
                # 继续搜索下一行
                backtrack(board, row+1)
                # 撤销当前选择
                board[row][col] = 0
    backtrack(board, 0)
    return res

使用示例：

res = solve_n_queens(4)
for solution in res:
    print(solution)

输出结果：

[".Q..", "...Q", "Q...", "..Q."]
["..Q.", "Q...", "...Q", ".Q.."]