n皇后问题python
时间: 2023-06-30 12:10:08 浏览: 57
n皇后问题是一个经典的回溯算法问题,用于解决在nxn的棋盘上放置n个皇后,使得它们不互相攻击。
以下是一个使用Python语言实现的n皇后问题的代码示例:
```python
def is_valid(board, row, col, n):
# 检查列是否有冲突
for i in range(n):
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 solve(board, row, n):
if row == n:
return True
for col in range(n):
if is_valid(board, row, col, n):
board[row][col] = 1
if solve(board, row+1, n):
return True
board[row][col] = 0
return False
def n_queens(n):
board = [[0 for _ in range(n)] for _ in range(n)]
if solve(board, 0, n):
for row in board:
print(row)
else:
print("No solution exists")
# 测试
n_queens(4)
```
输出结果为:
```
[0, 1, 0, 0]
[0, 0, 0, 1]
[1, 0, 0, 0]
[0, 0, 1, 0]
```
该代码使用了回溯算法,对每一行逐个尝试放置皇后。在每一列放置之前,先进行检查,确保在该列、左上对角线和右上对角线上都没有其他皇后。如果检查通过,则在该位置放置皇后,并递归调用自身,继续放置下一行的皇后。如果递归调用返回True,则表示已找到解决方案,否则表示该位置无法放置皇后,需要回溯到上一行重新尝试其他位置。