c++八皇后问题解法
时间: 2023-10-18 10:32:04 浏览: 54
八皇后问题是一个经典的算法问题,目标是在一个8x8的棋盘上放置8个皇后,使得它们互相之间不能相互攻击。这里给出一种常见的解法,使用回溯算法实现:
1. 创建一个8x8的二维数组作为棋盘,初始化所有元素为0,表示空格。
2. 从第一行开始,逐行放置皇后。对于每一行,从左到右遍历每个列,尝试将皇后放置在当前位置。
3. 如果当前位置可以放置皇后(即不会与已经放置的皇后相互攻击),将当前位置标记为1,并进入下一行。
4. 如果当前位置无法放置皇后,则回溯到上一行,继续尝试下一个列。
5. 当所有皇后都放置完毕时,得到一个解。可以将解存储起来或进行其他操作。
6. 继续回溯,寻找其他解法。
下面是一个简单的示例代码:
```python
def is_safe(board, row, col):
# 检查当前位置是否与已经放置的皇后冲突
# 检查列
for i in range(row):
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 < 8:
if board[i][j] == 1:
return False
i -= 1
j += 1
return True
def solve_n_queens():
board = [[0] * 8 for _ in range(8)]
solutions = []
def backtrack(row):
if row == 8:
# 找到一个解,将棋盘状态添加到结果列表中
solutions.append([row[:] for row in board])
return
for col in range(8):
if is_safe(board, row, col):
board[row][col] = 1 # 放置皇后
backtrack(row + 1) # 继续下一行
board[row][col] = 0 # 撤销放置的皇后
backtrack(0)
return solutions
# 调用函数并打印所有解法
solutions = solve_n_queens()
for solution in solutions:
for row in solution:
print(row)
print()
```
这段代码会输出所有的八皇后问题解法,每个解法是一个8x8的棋盘,其中1表示皇后的位置,0表示空格。希望这可以帮助到你!