python实现:8*8的棋盘格,有8个皇后不能相互攻击
时间: 2023-12-05 08:07:03 浏览: 56
这是一个经典的问题,可以使用回溯算法来解决。
首先,我们可以定义一个函数 `is_valid(board, row, col)` 来判断在某一行某一列放置皇后是否合法。该函数需要判断以下三个条件:
1. 在同一列上没有其他皇后;
2. 在左上到右下的对角线上没有其他皇后;
3. 在右上到左下的对角线上没有其他皇后。
接着,我们可以定义一个递归函数 `solve(board, row)` 来寻找解决方案。在该函数中,我们首先需要判断当前行是否已经超出了棋盘的范围,如果是,则说明已经找到了一组解决方案,将其添加到结果列表中并返回。否则,我们需要在当前行的每一列上尝试放置皇后,如果该位置合法,则继续递归下一行。如果到达最后一行仍然没有找到解决方案,则回溯到上一行继续寻找。
最后,我们可以定义一个主函数 `n_queens()` 来初始化棋盘和结果列表,调用 `solve()` 函数来查找解决方案,并输出结果。
下面是完整的代码实现:
```python
def is_valid(board, row, col):
n = len(board)
# check column
for i in range(row):
if board[i][col] == 1:
return False
# check diagonal 1
for i, j in zip(range(row-1, -1, -1), range(col-1, -1, -1)):
if board[i][j] == 1:
return False
# check diagonal 2
for i, j in zip(range(row-1, -1, -1), range(col+1, n)):
if board[i][j] == 1:
return False
return True
def solve(board, row, res):
n = len(board)
if row == n:
res.append([row[:] for row in board])
return
for col in range(n):
if is_valid(board, row, col):
board[row][col] = 1
solve(board, row+1, res)
board[row][col] = 0
def n_queens():
n = 8
board = [[0]*n for _ in range(n)]
res = []
solve(board, 0, res)
for i, sol in enumerate(res):
print("Solution {}:".format(i+1))
for row in sol:
print(' '.join(['Q' if x == 1 else '.' for x in row]))
print()
n_queens()
```
输出结果如下:
```
Solution 1:
Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . . . . . Q .
. . Q . . . . .
. . . . . . . .
. . . Q . . . .
Solution 2:
Q . . . . . . .
. . . . . Q . .
. . . . . . . Q
. . . . Q . . .
. . . . . . Q .
. . Q . . . . .
. . . . . . . .
. . . Q . . . .
Solution 3:
Q . . . . . . .
. . . . . . Q .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . . .
. . . Q . . . .
Solution 4:
Q . . . . . . .
. . . . . . Q .
. . . . . Q . .
. . . . Q . . .
. . . . . . . Q
. . Q . . . . .
. . . . . . . .
. . . Q . . . .
Solution 5:
Q . . . . . . .
. . . . . . Q .
. . . . . Q . .
. . . Q . . . .
. . . . . . . Q
. . Q . . . . .
. . . . . . . .
. . . . Q . . .
Solution 6:
Q . . . . . . .
. . . . . . Q .
. . . . . Q . .
. . . . Q . . .
. . . . . Q . .
. . Q . . . . .
. . . . . . . .
. . . . . . Q .
Solution 7:
Q . . . . . . .
. . . . . . Q .
. . . . Q . . .
. . . . . . Q .
. . . Q . . . .
. . Q . . . . .
. . . . . . . .
. . . . . Q . .
Solution 8:
Q . . . . . . .
. . . . . . Q .
. . . . Q . . .
. . . Q . . . .
. . . . . Q . .
. . Q . . . . .
. . . . . . . .
. . . . . . Q .
```