回溯 8 Queens Python 问题
Backtracking 8 Queens Python problems
我已经开始在 Python 中用回溯解决 8 皇后问题。一切都很好。它甚至打印出第一个答案。然而，它在第一次回溯尝试中卡住了。
任务听起来是这样的：
实现一个 Python 函数来解决 8 皇后难题。 8 皇后拼图包括在棋盘上放置 8 个皇后，这样 none 个皇后可以捕获任何其他皇后。请注意，皇后可以在任何方向上正交或沿对角线移动。
您应该实现一个函数 solve()，当调用该函数时，它会打印拼图的第一个解，然后等待输入。一旦用户按下“enter”，就会打印下一个解决方案，依此类推。
- 您的程序应该能够找到拼图的所有解决方案，并且每个解决方案只能找到一次。 '
- 修改您的程序应该很容易，因此它适用于不同的电路板尺寸。提示：
- 任意一行，恰好有一个皇后。因此，您只需要计算 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 的建议，现在我得到了 Queen 的随机星座，但我完全摆脱了递归。
```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)
这是一个如何递归解决 8 皇后区问题的示例，使用一个简单的列表来表示棋盘。一个列表如[8, 4, 1, 3, 6, 2, 7, 5]表示一个棋盘从上到下的8行，Q在最上面一行的第8列，第4列是Q第 7 行，第 6 行的第 1 列...和最后一行的第 5 列。
解决方案是从空板开始 [] 通过将 Q 放在下一行不能被取走的列位置。可能的位置是之前尚未使用的列（这是函数 solve 中的 for 循环）。对于这些可能的列位置中的每一个，函数 issafe 检查该位置是否安全，不会被棋盘上已有的 Q 沿对角线占据。如果该位置是安全的，则解决方案板被另一行扩展并且解决方案递归直到板被填满（len(board) == boardsize），此时解决方案计数增加并显示板。
请注意，函数 solve 适用于任何大小的方形棋盘 - 所需大小作为参数传递给 solve，函数 returns 解决方案的总数找到了。
希望这有助于解释如何在没有 numpy 的情况下递归解决 8 皇后区问题。
def display(solution_number, board):
row = '| ' * len(board) + '|'
hr = '+---' * len(board) + '+'
for col in board:
print(hr)
print(row[:col*4-3],'Q',row[col*4:])
print(f'{hr}\n{board}\nSolution - {solution_number}\n')
def issafe(q, board, x=1):
if not board: return True
if board[-1] in [q+x,q-x]: return False
return issafe(q, board[:-1], x+1)
def solve(boardsize, board=[], solutions_found=0):
if len(board) == boardsize:
solutions_found += 1
display(solutions_found, board)
else:
for q in [col for col in range(1,boardsize+1) if col not in board]:
if issafe(q,board):
solutions_found = solve(boardsize, board + [q], solutions_found)
return solutions_found
if __name__ == '__main__':
solutions = solve(8)
print(f'{solutions} solutions found')
您提到使用 yield - 这也是可能的，并且会将 solve 转换为生成器，一次生成一个解决方案。然后您的程序可以使用 for 循环依次接收每个解决方案并根据需要进行处理。以下 yield 解决方案适用于 Python v.3.3 及更高版本，因为它使用 yield from:
def display(solution_number, board):
row = '| ' * len(board) + '|'
hr = '+---' * len(board) + '+'
for col in board:
print(hr)
print(row[:col*4-3],'Q',row[col*4:])
print(f'{hr}\n{board}\nSolution - {solution_number}\n')
def issafe(q, board, x=1):
if not board: return True
if board[-1] in [q+x,q-x]: return False
return issafe(q, board[:-1], x+1)
def solve(boardsize, board=[]):
if len(board) == boardsize:
yield board
else:
for q in [col for col in range(1,boardsize+1) if col not in board]:
if issafe(q,board):
yield from solve(boardsize, board + [q])
if __name__ == '__main__':
for solutionnumber, solution in enumerate(solve(8)):
display(solutionnumber+1, solution)
如果递归函数 issafe 看起来令人困惑，这里是 non-recursive 版本：
def issafe(q, board):
x = len(board)
for col in board:
if col in [q+x,q-x]: return False
x -= 1
return True
我已经开始在 Python 中用回溯解决 8 皇后问题。一切都很好。它甚至打印出第一个答案。然而，它在第一次回溯尝试中卡住了。
任务听起来是这样的：
实现一个 Python 函数来解决 8 皇后难题。 8 皇后拼图包括在棋盘上放置 8 个皇后，这样 none 个皇后可以捕获任何其他皇后。请注意，皇后可以在任何方向上正交或沿对角线移动。
您应该实现一个函数 solve()，当调用该函数时，它会打印拼图的第一个解，然后等待输入。一旦用户按下“enter”，就会打印下一个解决方案，依此类推。
- 您的程序应该能够找到拼图的所有解决方案，并且每个解决方案只能找到一次。 '
- 修改您的程序应该很容易，因此它适用于不同的电路板尺寸。提示：
- 任意一行，恰好有一个皇后。因此，您只需要计算 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 的建议，现在我得到了 Queen 的随机星座，但我完全摆脱了递归。
```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)
这是一个如何递归解决 8 皇后区问题的示例，使用一个简单的列表来表示棋盘。一个列表如[8, 4, 1, 3, 6, 2, 7, 5]表示一个棋盘从上到下的8行，Q在最上面一行的第8列，第4列是Q第 7 行，第 6 行的第 1 列...和最后一行的第 5 列。
解决方案是从空板开始 [] 通过将 Q 放在下一行不能被取走的列位置。可能的位置是之前尚未使用的列（这是函数 solve 中的 for 循环）。对于这些可能的列位置中的每一个，函数 issafe 检查该位置是否安全，不会被棋盘上已有的 Q 沿对角线占据。如果该位置是安全的，则解决方案板被另一行扩展并且解决方案递归直到板被填满（len(board) == boardsize），此时解决方案计数增加并显示板。
请注意，函数 solve 适用于任何大小的方形棋盘 - 所需大小作为参数传递给 solve，函数 returns 解决方案的总数找到了。
希望这有助于解释如何在没有 numpy 的情况下递归解决 8 皇后区问题。
def display(solution_number, board):
row = '| ' * len(board) + '|'
hr = '+---' * len(board) + '+'
for col in board:
print(hr)
print(row[:col*4-3],'Q',row[col*4:])
print(f'{hr}\n{board}\nSolution - {solution_number}\n')
def issafe(q, board, x=1):
if not board: return True
if board[-1] in [q+x,q-x]: return False
return issafe(q, board[:-1], x+1)
def solve(boardsize, board=[], solutions_found=0):
if len(board) == boardsize:
solutions_found += 1
display(solutions_found, board)
else:
for q in [col for col in range(1,boardsize+1) if col not in board]:
if issafe(q,board):
solutions_found = solve(boardsize, board + [q], solutions_found)
return solutions_found
if __name__ == '__main__':
solutions = solve(8)
print(f'{solutions} solutions found')
您提到使用 yield - 这也是可能的，并且会将 solve 转换为生成器，一次生成一个解决方案。然后您的程序可以使用 for 循环依次接收每个解决方案并根据需要进行处理。以下 yield 解决方案适用于 Python v.3.3 及更高版本，因为它使用 yield from:
def display(solution_number, board):
row = '| ' * len(board) + '|'
hr = '+---' * len(board) + '+'
for col in board:
print(hr)
print(row[:col*4-3],'Q',row[col*4:])
print(f'{hr}\n{board}\nSolution - {solution_number}\n')
def issafe(q, board, x=1):
if not board: return True
if board[-1] in [q+x,q-x]: return False
return issafe(q, board[:-1], x+1)
def solve(boardsize, board=[]):
if len(board) == boardsize:
yield board
else:
for q in [col for col in range(1,boardsize+1) if col not in board]:
if issafe(q,board):
yield from solve(boardsize, board + [q])
if __name__ == '__main__':
for solutionnumber, solution in enumerate(solve(8)):
display(solutionnumber+1, solution)
如果递归函数 issafe 看起来令人困惑，这里是 non-recursive 版本：
def issafe(q, board):
x = len(board)
for col in board:
if col in [q+x,q-x]: return False
x -= 1
return True