回溯法八皇后问题python

### 使用Python通过回溯法解决八皇后问题

#### 实现思路

八皇后问题的目标是在8×8的国际象棋棋盘上放置八个皇后，使得它们互不攻击。这意味着任何两个皇后都不能位于同一行、同一列或同一对角线上[^3]。

为了实现这一目标，可以采用回溯算法来逐步尝试每一种可能的位置组合。如果当前的选择导致冲突，则撤销该选择并尝试其他可能性。这种方法能够有效地遍历所有可行解，并最终找到满足条件的一个或多于一个解。

具体来说，在每一层递归调用中：

- 尝试将一个新皇后放在第`row`行中的某一列；
- 对于每一个候选位置，检查它是否会与其他已放置好的皇后发生冲突；
- 如果当前位置安全，则继续处理下一行(`row+1`)；如果不安全则跳过此位置；
- 当到达最后一行之后仍然没有遇到冲突时说明找到了一组有效布局；
- 反之如果没有更多可用选项可选且回退至前一层继续探索其它路径直到完成整个搜索过程为止。

以下是具体的Python代码实现：

def solve_n_queens(n):
    solutions = []
    
    def is_not_under_attack(row, col, queens):
        # Check column and diagonals for conflicts with previously placed queens.
        for r, c in enumerate(queens):
            if r == row or \
               c == col or \
               abs(r - row) == abs(c - col):  # Diagonal check
                return False
        return True
    
    def place_queen(row, queens):
        if row == n:
            solutions.append(['.' * i + 'Q' + '.' * (n-i-1) for i in queens])
            return
        
        for col in range(n):
            if is_not_under_attack(row, col, queens):
                place_queen(row + 1, queens + [col])

    place_queen(0, [])
    return solutions


if __name__ == "__main__":
    board_size = 8
    result = solve_n_queens(board_size)

    print(f"Found {len(result)} solution(s).")
    for idx, sol in enumerate(result[:min(len(result), 5)]):  # Print up to first five solutions only as an example
        print(f"\nSolution #{idx + 1}:")
        for line in sol:
            print(line)

这段代码定义了一个名为`solve_n_queens()` 的函数用于解决问题。内部有两个辅助函数：一个是用来判断给定坐标是否受到攻击 `is_not_under_attack()`,另一个则是核心逻辑所在的地方——递归地放置皇后 `place_queen()` 。最后部分展示了如何执行这个方法以及打印出一些样例解答。