我正在写一个python类来寻找8皇后问题的解决方案。如何在solve
方法中正确实现回溯?我认为递归应该可以工作,但是,在第一次尝试没有找到解决方案之后,程序就会停止,并且回溯不会发生。所有助手方法都正常工作。你知道吗
EMPTY = 0
QUEEN = 1
RESTRICTED = 2
class Board:
# initializes a 8x8 array
def __init__ (self):
self.board = [[EMPTY for x in range(8)] for y in range(8)]
# pretty prints board
def printBoard(self):
for row in self.board:
print(row)
# places a queen on a board
def placeQueen(self, x, y):
# restricts row
self.board[y] = [RESTRICTED for i in range(8)]
# restricts column
for row in self.board:
row[x] = RESTRICTED
# places queen
self.board[y][x] = QUEEN
self.fillDiagonal(x, y, 0, 0, -1, -1) # restricts top left diagonal
self.fillDiagonal(x, y, 7, 0, 1, -1) # restructs top right diagonal
self.fillDiagonal(x, y, 0, 7, -1, 1) # restricts bottom left diagonal
self.fillDiagonal(x, y, 7, 7, 1, 1) # restricts bottom right diagonal
# restricts a diagonal in a specified direction
def fillDiagonal(self, x, y, xlim, ylim, xadd, yadd):
if x != xlim and y != ylim:
self.board[y + yadd][x + xadd] = RESTRICTED
self.fillDiagonal(x + xadd, y + yadd, xlim, ylim, xadd, yadd)
# recursively places queens such that no queen shares a row or
# column with another queen, or in other words, no queen sits on a
# restricted square. Should solve by backtracking until solution is found.
def solve(self, queens):
if queens == 8:
return True
for i in range(8):
if self.board[i][queens] == EMPTY:
self.placeQueen(queens, i)
if self.solve(queens - 1):
return True
self.board[i][queens] = RESTRICTED
return False
b1 = Board()
b1.solve(7)
b1.printBoard()
我的问题是,在加入女王之前,董事会缺乏一份深入的副本,还是仅仅缺乏回溯?你知道吗
两者都有:在你的整个计划中,你只有一份董事会的副本。您尽可能地填充它,直到所有的方块都被占用或限制;搜索失败,您从
solve
返回。如果没有重置电路板的机制,程序将结束。你知道吗回溯将使这变得简单,代价是多个中间板。而不是有一个单一的董事会对象。。。制作一个深度副本,放置皇后,标记适当的限制方块,并将修改后的副本传递到下一级。如果返回失败,让副本自然蒸发,成为局部变量。你知道吗
相关问题 更多 >
编程相关推荐