N皇后问题求解：Python代码实现

N皇后问题是一个经典的回溯算法问题，它要求将n个皇后放置在n×n的棋盘上，使得皇后彼此之间不能相互攻击。即任何两个皇后都不能处于同一行、同一列或同一对角线上。

本文将提供一个Python代码实现，并详细解释其工作原理。

算法思路

使用cols数组记录皇后位置: 我们使用一个长度为n的列表cols来记录每一行中皇后所在的列数。初始时，每行都没有皇后，即cols=[-1]*n。
递归枚举: 从第一行开始，依次枚举该行中每一列。如果该列已经有皇后了，就跳过；否则，我们就将该列作为该行皇后的位置，将cols数组中相应的位置更新为该列。
递归处理下一行: 递归处理下一行，直到最后一行处理完毕，我们就得到了一个合法的方案。
合法性判断: 在处理下一行时，我们需要先判断当前列是否可行（即cols中是否已经存在该列），如果存在就不能选择该列。其次，我们需要判断右上方和左上方是否存在皇后，如果存在也不能选择该列。这可以通过计算行号与列号之差或之和的值是否相等来判断。
方案转化: 当我们得到一个合法的方案时，我们将其转化为一个字符串列表，其中每个字符串表示一行，皇后所在的位置用'Q'表示，空位用'.'表示。
存储所有方案: 最后将所有合法方案存储在一个列表中，并返回该列表。

代码实现

import sys
from collections import deque

def solveNQueens(n: int) -> List[List[str]]:
    def is_valid(row, col):
        # 检查该列是否已经有皇后
        if cols[col] != -1:
            return False
        # 检查右上方和左上方是否存在皇后
        for i in range(row):
            if abs(row - i) == abs(col - cols[i]):
                return False
        return True

    def backtrack(row):
        if row == n:
            # 所有行都已放置皇后，得到一个合法方案
            solution = [['.'] * n for _ in range(n)]
            for i in range(n):
                solution[i][cols[i]] = 'Q'
            result.append([''.join(row) for row in solution])
            return

        # 尝试将皇后放置在该行的每一列
        for col in range(n):
            if is_valid(row, col):
                cols[col] = row
                backtrack(row + 1)
                cols[col] = -1  # 回溯，将该列恢复为初始状态

    result = []
    cols = [-1] * n
    backtrack(0)
    return result

if __name__ == '__main__':
    n = int(sys.stdin.readline().strip())
    print(solveNQueens(n))

代码解释

solveNQueens(n: int) 函数: 该函数接受一个整数n作为参数，表示棋盘的大小。
is_valid(row, col) 函数: 该函数用于判断将皇后放置在第row行第col列是否合法。
backtrack(row) 函数: 该函数使用递归来尝试将皇后放置在每一行。
result 列表: 用于存储所有合法的方案。
cols 列表: 用于记录每一行皇后所在的列数。

示例

输入：4 输出：

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

总结

本文介绍了如何使用Python代码解决N皇后问题，并提供了详细的算法解释和示例代码。该代码使用cols数组和递归来判断皇后放置的合法性，并将所有合法的方案存储在一个列表中，最终返回该列表。希望本文能够帮助您理解N皇后问题的求解过程和代码实现。