我已经开始用 Python 回溯解决 8 个皇后问题。一切都很好。它甚至打印出第一个答案。然而，它在第一次回溯尝试中陷入了困境。
任务听起来是这样的：
实现一个解决 8 个皇后谜题的 Python 函数。8皇后拼图包括将8个皇后放在棋盘上，这样任何一个皇后都无法捕获任何其他皇后。请注意，皇后可以在任何方向上正交或对角移动。
你应该实现一个函数solve()，当被调用时，它会打印出第一个谜题的解，然后等待输入。一旦用户按下“输入”，就会打印下一个解决方案，依此类推。
- 您的程序应该能够找到该难题的所有解决方案，并且每个解决方案只能找到一次。'
- 修改程序应该很容易，因此它适用于不同的电路板尺寸。提示：
- 在任何一排中，只有一个皇后。因此，您需要计算的只是可以放置 8 个皇后的列。
- 你应该实现一个递归函数solve(n)，它为第n+1个皇后找到一个位置，然后为第n+1个皇后递归调用自己（除非所有皇后都已放置）。它应该系统地探索使用回溯的所有可能性。
- 允许（并鼓励）定义额外的函数（除了 solve() ）以在必要时提高代码的质量。
import numpy as np
grid = np.zeros((8, 8), dtype = int)
def possible(y, n):
global solved
global grid
for i in range(0, 8):
if grid[y][i] == n:
return False
try:
for item in solved[str(y)]:
if grid[y].all() == item.all():
return False
except KeyError:
return True
return True
max_y = 7
max_x = 7
def print_grid():
global grid
for line in grid:
for square in line:
if square == 0:
print(".", end = " ")
else :
print("Q", end = " ")
print()
solved = {}
def prefilled_solved():
global solved
for i in range(0, len(grid[0])):
solved[f"{str(i)}"] = []
def solve(y=0):
global grid
global solved
while y < 8:
for x in range(0, 8):
if grid[y][x] == 0:
if possible(x, 1):
grid[y][x] = 1
solved[f"{str(y)}"].append(grid[y])
y += 1
solve(y)
#y -= 1 or y = 0 or y -=2
# backtracking - bad choice
# grid[y][x] = 0
print_grid()
print(grid)
return
input("More?")
if __name__ == '__main__':
prefilled_solved()
solve()
我遵循了@mkam 的建议，现在我有了皇后的随机星座，但我完全摆脱了递归。
```import numpy as np
grid = np.zeros((8, 8), dtype = int)
from random import randint, shuffle, choice
from itertools import permutations
constellations_drawn = []
def print_grid():
global grid
for line in grid:
for square in line:
if square == 0:
print(".", end = " ")
else :
print("Q", end = " ")
print()
solved = []
def prefilled_solved():
global solved
new_board = ['1', '2', '3', '4', '5', '6', '7', '8']
new_board_i = ''.join(new_board)
solved = permutations(new_board_i, 8)
def solve(y=0):
global grid
global solved
global constellations_drawn
list_solved = list(solved)
len_solved = len(list_solved)
board_drawn = list_solved[randint(0, len_solved-1)]
board_drawn_str = ''.join(board_drawn)
while board_drawn_str in constellations_drawn:
board_drawn = list_solved[randint(0, len_solved - 1)]
new_board_list = [int(item) for item in board_drawn]
for i, x in enumerate(new_board_list):
if grid[i-1][x-1] == 0:
grid[i-1][x-1] = 1
#y += 1
#solve(y)
#y -= 1 or y = 0 or y -=2
# backtracking - bad choice
# grid[y][x] = 0
constellations_drawn.append(board_drawn_str)
print_grid()
print(grid)
return
input("More?")
if __name__ == '__main__':
prefilled_solved()
solve()
I've merged the code of @mkam and mine. And it works. I still use numpy ndarray.
import numpy as np
from numpy.core._multiarray_umath import ndarray
def print_grid(solutions_found, board) -> None:
line: ndarray
len_board = len(board)
grid: ndarray = np.zeros((len_board, len_board), dtype=int)
for i, number in enumerate(board):
grid[i - 1][number - 1] = 1
for line in grid:
for square in line:
if square == 0:
print(".", end=" ")
else:
print("Q", end=" ")
print()
print(f'Solution - {solutions_found}')
def solve(boardsize, board=[], solutions_found=0):
if len(board) == boardsize:
solutions_found += 1
print_grid(solutions_found, board)
else:
for q in [col for col in range(1, boardsize + 1) if col not in board]:
if is_safe(q, board):
solutions_found = solve(boardsize, board + [q], solutions_found)
return solutions_found
def is_safe(q, board, x=1):
if not board:
return True
if board[-1] in [q + x, q - x]:
return False
return is_safe(q, board[:-1], x + 1)
if __name__ == '__main__':
solve(8)