N皇后
仅供学习
一、问题描述
n 皇后问题是一个经典的组合问题，可以通过回溯算法来解决。
二、python代码
def solve_n_queens(n): def can_place(row, col): # 检查这一行之前是否有列可以放置皇后 for i in range(row): if board[i] == col or abs(board[i] - col) == row - i: return False return True def solve(row=0): if row == n: result.append([''.join(['Q' if c == i else '.' for i in range(n)]) for c in board]) return for col in range(n): if can_place(row, col): board[row] = col solve(row + 1) # 回溯，移除这一行的皇后 board[row] = -1 result = [] board = [-1] * n # 初始化棋盘，-1 表示没有皇后 solve() return result # 调用函数，例如 n=4 n = 4 solutions = solve_n_queens(n) for solution in solutions: for row in solution: print(row) print() # 打印空行以分隔不同的解决方案
三、代码讲解
这段代码定义了一个 solve_n_queens 函数，它接受一个整数 n 作为输入，并返回所有可能的 n 皇后问题的解决方案。函数内部使用了递归和回溯算法来寻找所有可能的放置方式。
- can_place 函数用于检查在给定行和列是否可以放置一个皇后。
- solve 是一个递归函数，它尝试在每一行放置一个皇后，并递归地解决剩余的行。
- result 用于存储所有找到的解决方案。
- board 是一个列表，用于表示当前棋盘的状态。
调用 solve_n_queens(n) 并传入一个整数 n 时，它会返回一个包含所有解决方案的列表。每个解决方案都是一个表示棋盘的字符串列表，其中 ‘Q’ 表示皇后的位置，‘.’ 表示空位。
