回溯 8 Queens Python 问题 [英] Backtracking 8 Queens Python problems
问题描述
我已经开始使用 Python 中的回溯解决 8 个皇后问题.一切都很好&美好的.它甚至打印出了第一个答案.然而，它坚持第一次回溯尝试.
任务听起来是这样的:
实现一个 Python 函数来解决 8 个皇后的难题.8皇后拼图包括在棋盘上放置8个皇后，因此，没有一个皇后可以捕获任何其他皇后.请注意，皇后可以向任何方向正交或对角移动.
你应该实现一个函数 solve() ，当它被调用时，它会打印出谜题的第一个解，然后等待输入.一旦用户按下回车"，就会打印下一个解决方案，依此类推.
-您的程序应该能够找到谜题的所有解决方案，并且每个解决方案只能找到一次. '
- 修改程序应该很容易，因此它适用于不同的电路板尺寸.提示:
- 在任何一行中，只有一个皇后.因此，您只需要计算可以放置 8 个皇后中的每一个的列.
- 你应该实现一个递归函数solve(n)，它为第n+1个皇后找到一个位置，然后为第n+1个皇后递归调用自己(除非所有的皇后都被放置了).它应该使用回溯系统地探索所有可能性.
- 允许(并鼓励)您定义额外的函数(solve() 除外)以在必要时提高代码质量.
<预><代码>将 numpy 导入为 np网格 = np.zeros((8, 8), dtype = int)定义可能(y，n):全球解决全球网格对于范围内的 i (0, 8):如果网格[y][i] == n:返回错误尝试:对于已解决 [str(y)] 中的项目:如果 grid[y].all() == item.all():返回错误除了 KeyError:返回真返回真max_y = 7max_x = 7定义打印网格():全球网格对于网格中的线:对于直线方形:如果平方 == 0:打印(."，结束=")别的 :打印(Q"，结束=")打印()解决了 = {}def prefill_solved():全球解决对于范围内的 i(0, len(grid[0])):解决了[f{str(i)}"] = []定义解决(y = 0):全球网格全球解决当 y <8:对于范围内的 x (0, 8):如果网格[y][x] == 0:如果可能(x，1):网格[y][x] = 1解决了[f{str(y)}"].append(grid[y])y += 1解决(y)#y -= 1 或 y = 0 或 y -=2# 回溯 - 错误的选择# 网格[y][x] = 0打印网格()打印(网格)返回输入(更多?")如果 __name__ == '__main__':prefill_solved()解决()我遵循了@mkam 的建议，现在我得到了随机的皇后星座，但我已经完全摆脱了递归.
```import numpy as np网格 = np.zeros((8, 8), dtype = int)从随机导入 randint、shuffle、选择从 itertools 导入排列constellations_drawn = []定义打印网格():全球网格对于网格中的线:对于直线方形:如果平方 == 0:打印(."，结束=")别的 :打印(Q"，结束=")打印()解决了 = []def prefill_solved():全球解决new_board = ['1', '2', '3', '4', '5', '6', '7', '8']new_board_i = ''.join(new_board)解决 = 排列(new_board_i，8)定义解决(y = 0):全球网格全球解决全球星座_drawnlist_solved = 列表(已解决)len_solved = len(list_solved)board_drawn = list_solved[randint(0, len_solved-1)]board_drawn_str = ''.join(board_drawn)而constellations_drawn中的board_drawn_str:board_drawn = list_solved[randint(0, len_solved - 1)]new_board_list = [int(item) for board_drawn 中的项目]对于 i, x in enumerate(new_board_list):如果网格[i-1][x-1] == 0:网格[i-1][x-1] = 1#y += 1#解决(y)#y -= 1 或 y = 0 或 y -=2# 回溯 - 错误的选择# 网格[y][x] = 0constellations_drawn.append(board_drawn_str)打印网格()打印(网格)返回输入(更多?")如果 __name__ == '__main__':prefilled_solved()解决()<预><代码>我已经合并了@mkam 和我的代码.它有效.我仍然使用 numpy ndarray.
将 numpy 导入为 np从 numpy.core._multiarray_umath 导入 ndarraydef print_grid(solutions_found, board) ->没有任何:行:ndarraylen_board = len(板)网格:ndarray = np.zeros((len_board, len_board), dtype=int)对于我，枚举(板)中的数字:网格[i - 1][数字 - 1] = 1对于网格中的线:对于直线方形:如果平方 == 0:打印(."，结束=")别的:打印(Q"，结束=")打印()打印(f'解决方案 - {solutions_found}')def解决(板尺寸，板= []，解决方案_发现= 0):如果 len(board) == boardsize:解决方案_发现 += 1打印网格(解决方案找到，板)别的:对于 q in [col for col in range(1, boardsize + 1) if col not in board]:如果 is_safe(q, board):Solutions_found = 解决(板尺寸，板 + [q]，解决方案_发现)返回solutions_founddef is_safe(q, board, x=1):如果没有登机:返回真如果 board[-1] 在 [q + x, q - x] 中:返回错误返回 is_safe(q, board[:-1], x + 1)如果 __name__ == '__main__':解决(8)这是一个如何递归解决 8-Queens 问题的示例，使用一个简单的列表来表示板.像[8, 4, 1, 3, 6, 2, 7, 5]这样的列表代表一个棋盘从上到下的8行，顶行第8列有Q，第4列是Q第 7 行，第 6 行的第 1 列……和底行的第 5 列.
一个解决方案是从一个空板[] 开始构建的，方法是在下一行的列位置放置一个 Q，在该位置它不能被取走.可能的位置是之前尚未被采用的列(这是函数 solve 中的 for 循环).对于这些可能的列位置中的每一个，函数 issafe 检查该位置是否安全，不会被棋盘上的 Q 对角占据.如果位置是安全的，则解决方案板扩展另一行并且解决方案递归直到板被填满(len(board) == boardsize)，此时解决方案计数增加并且显示板.
请注意，solve 函数适用于任何大小的正方形棋盘——所需的大小作为参数传递给 solve，该函数返回解的总数找到了.
希望这有助于解释如何在没有 numpy 的情况下递归解决 8-Queens 问题.
def display(solution_number, board):行 = '|' * len(板) + '|'hr = '+---' * len(board) + '+'对于船上的col:打印(小时)打印(行[:col*4-3],'Q',行[col*4:])打印(f'{hr}\n{board}\nSolution - {solution_number}\n')def issafe(q, board, x=1):如果没有登机:返回 True如果 [q+x,q-x] 中的 board[-1]:返回 False返回 issafe(q, board[:-1], x+1)def解决(板尺寸，板= []，解决方案_发现= 0):如果 len(board) == boardsize:解决方案_发现 += 1显示(solutions_found，板)别的:对于 q in [col for col in range(1,boardsize+1) if col not in board]:如果是安全的(q，板):Solutions_found = 解决(板尺寸，板 + [q]，解决方案_发现)返回solutions_found如果 __name__ == '__main__':解决方案 = 解决(8)打印(f'{解决方案}找到解决方案')您提到使用 yield - 这也是可能的，并且会将 solve 转换为生成器，一次生成一个解决方案.然后，您的程序可以使用 for 循环依次接收每个解决方案并根据需要对其进行处理.以下 yield 解决方案适用于 Python v.3.3 以上版本，因为它使用 yield from:
def display(solution_number, board):行 = '|' * len(板) + '|'hr = '+---' * len(board) + '+'对于船上的col:打印(小时)打印(行[:col*4-3],'Q',行[col*4:])打印(f'{hr}\n{board}\nSolution - {solution_number}\n')def issafe(q, board, x=1):如果没有登机:返回 True如果 [q+x,q-x] 中的 board[-1]:返回 False返回 issafe(q, board[:-1], x+1)def解决(板尺寸，板= []):如果 len(board) == boardsize:收益板别的:对于 q in [col for col in range(1,boardsize+1) if col not in board]:如果是安全的(q，板):解决收益(板尺寸，板 + [q])如果 __name__ == '__main__':对于solutionnumber，enumerate(solve(8))中的解决方案:显示(解决方案编号+1，解决方案)如果递归函数 issafe 看起来令人困惑，这里是一个非递归版本:
def issafe(q, board):x = len(板)对于船上的col:如果 [q+x,q-x] 中的 col:返回 Falsex -= 1返回真I've started solving the 8 queens problem with backtracking in Python. Everything is nice & fine. It even printed out the first answer. However, it stuck itself on its first backtracking try.
The task sounded in that way:
Implement a Python function that solves the 8 queens puzzle. The 8 queen puzzle consists of placing 8 queens on a chess board, so that, none of the queens could capture any other. Note that queens can move orthogonally or diagonally in any direction.
You should implement a function solve() that when called, it prints the first solution of the puzzle and then it awaits for input. Once the user presses ‘enter’, the next solution is printed, and so on.
- Your program should be able to find all the solutions for the puzzle and each solution only once. '
- It should be easy to modify your program, so that, it works for different board sizes. Hints:
- In any row, there is exactly one queen. Hence, all you need to compute is the column in which each of the 8 queens can be placed.
- You should implement a recursive function solve(n) that finds a place for nth+1 the queen and then calls itself recursively for the n+1 queen (unless all the queens have been placed). It should systematically explore all the possibilities using backtracking.
- You are allowed (and encouraged) to define extra functions (other than solve() ) to improve the quality of your code if necessary.
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()
I've followed the @mkam advice, Now I've got the random constellation of Queen but I've got rid of recursion altogether.
```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)
This is an example of how the 8-Queens problem can be solved recursively, using a simple list to represent the board. A list such as [8, 4, 1, 3, 6, 2, 7, 5] represents the 8 rows of a chessboard from top to bottom, with a Q in the 8th column of the top row, the 4th column of the 7th row, the 1st column of the 6th row ... and the 5th column of the bottom row.
A solution is built starting with an empty board [] by placing a Q in the next row in a column position where it cannot be taken. Possible positions are columns which have not already been taken earlier (this is the for loop in function solve). For each of these possible column positions, function issafe checks whether the position is safe from being taken diagonally by the Qs already on the board. If the position is safe, the solution board is extended by another row and the solution recurses until the board is filled (len(board) == boardsize), at which point the solution count is incremented and the board is displayed.
Note that the function solve works for any size of square chessboard - the desired size is passed as a parameter to solve, and the function returns the total number of solutions found.
Hope this helps explain how the 8-Queens problem can be solved recursively WITHOUT numpy.
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')
You mention using yield - this is also possible, and will transform solve into a generator, producing one solution at a time. Your program can then use a for loop to receive each solution in turn and process it as required. The following yield solution works with Python v.3.3 onwards because it uses 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)
If the recursive function issafe appears confusing, here is a non-recursive version:
def issafe(q, board):
x = len(board)
for col in board:
if col in [q+x,q-x]: return False
x -= 1
return True
这篇关于回溯 8 Queens Python 问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
