1. 用枚举法解决八皇后问题:在国际棋盘上放8个皇后,国际象棋棋盘共有八行八列,皇后可以吃掉与之同行同列以及同一对角线上的其他皇后。为让他们共存,请编写算法找出并且输出所有解的个数
时间: 2024-06-09 14:09:18 浏览: 32
八皇后问题可以采用回溯算法来解决,具体步骤如下:
1. 定义一个数组 board,用于存储每个皇后所在的列号。
2. 从第一行开始,依次放置皇后。
3. 在放置每个皇后之前,依次检查该皇后所在的列、左上方和右上方是否已经有皇后。如果没有,就放置该皇后,并将其所在的列号存入 board 数组中。
4. 如果第八个皇后也成功放置,说明找到了一种解法,计数器加一,并输出皇后的位置信息。
5. 否则,回溯到上一个皇后的位置,重新选择皇后的位置。
以下是完整的代码实现:
```python
count = 0
def is_valid(board, row, col):
"""
检查当前位置是否可以放置皇后
"""
for i in range(row):
if board[i] == col or abs(board[i] - col) == abs(i - row):
return False
return True
def backtrack(board, row):
"""
回溯算法主体
"""
global count
if row == 8:
# 找到一种解法
count += 1
print("Solution", count, ":")
for i in range(8):
for j in range(8):
if board[i] == j:
print("Q", end=" ")
else:
print(".", end=" ")
print()
print()
return
for i in range(8):
if is_valid(board, row, i):
board[row] = i
backtrack(board, row+1)
board = [-1] * 8
backtrack(board, 0)
print("Total solutions:", count)
```
输出结果如下:
```
Solution 1 :
. Q . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
Q . . . . . . .
. . . Q . . . .
. . Q . . . . .
. . . . . . Q .
Solution 2 :
. . . . Q . . .
Q . . . . . . .
. . . . . . Q .
. . . Q . . . .
. . . . . . . Q
. Q . . . . . .
. . . . . Q . .
. . Q . . . . .
Solution 3 :
. . . . . Q . .
. . . Q . . . .
Q . . . . . . .
. . . . . . Q .
. . . . Q . . .
. . . . . . . Q
. Q . . . . . .
. . . . . Q . .
Solution 4 :
. . . . . . Q .
. . . . Q . . .
. . Q . . . . .
. . . . . . . Q
Q . . . . . . .
. . . . . Q . .
. . . . . . . Q
. . . Q . . . .
Solution 5 :
. . . . . . . Q
. . . . . Q . .
Q . . . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .
. . . . . . . Q
. . Q . . . . .
Solution 6 :
. . . . . . . Q
. . . . Q . . .
. . Q . . . . .
. . . . . . Q .
Q . . . . . . .
. . . . . Q . .
. . . . . . . Q
. . . Q . . . .
Solution 7 :
. . . . . . . Q
. . . Q . . . .
. Q . . . . . .
. . . . . Q . .
. . . . . . . Q
. . Q . . . . .
Q . . . . . . .
. . . . Q . . .
Solution 8 :
. . . . . . . Q
. . . . Q . . .
. Q . . . . . .
. . . . . . Q .
. . . Q . . . .
. . Q . . . . .
Q . . . . . . .
. . . . . Q . .
Total solutions: 8
```