“自我”如何正确更新原始变量？ N皇后问题中的递归/回溯（Python）

Question

这是我的python程序，用于解决8皇后问题。除了打印解决方案的电路板的最后一步之外，所有步骤都可以正常工作。我使用递归/回溯功能在木板上填入皇后，直到找到解决方案为止。拥有解决方案的板对象是self，它是对b1的引用，因此我假设我初始化的原始板b1将被更新为包含最终解决的板，并打印解决方案使用printBoard。但是，b1未被更新，并且由于某些未知原因打印时，它拿着一块故障的电路板。

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, col):

        if col == -1:
            return True

        for i in range(8):
            if self.board[i][col] == EMPTY:
                temp = self.copy()

                if self.solve(col - 1):
                    return True

                temp.board[i][col] = RESTRICTED
                self = temp.copy()

        return False

    # deep copies a board onto another board
    def copy(self):
        copy = Board()

        for i in range(8):
            for j in range (8):
                copy.board[j][i] = self.board[j][i]

        return copy


b1 = Board()
b1.solve(7)
b1.printBoard()

我知道我的实际求解器正在工作，因为当我像这样添加printBoard时：

if col == -1:
    self.printBoard()
    return True

在solve方法中，打印出已解决的板。简而言之，为什么单板的self实例不更新b1？

Answer 1

我相信您的问题与在Solve方法中重新定义自我有关，我甚至不知道您为什么这样做。

请参阅此问题以获取更多详细信息：Is it safe to replace a self object by another object of the same type in a method?

像您一样重新分配自我不会重新分配“ b1”参考。因此，当您再次引用b1并执行printBoard时，您所引用的对象与“ self.printBoard（）”将在求解完成时所引用的对象不同。

我会退后一步，问问自己，为什么你要取代自我，以及从中获得什么。您可能也不需要，也不应该这样做。

Answer 2

我不确定这应该如何工作，因为从未调用过placeQueen。因此，我看不到按照建议的方式添加印刷品会形成一块成品板（我认为它是空的）。

除此之外，使用受限平方的想法可能行得通，但是在这里实现它的方式（没有撤消选项）效率不高；为每个内部循环复制一个全新的Board对象非常昂贵。对于所有麻烦，我们也可以对每步执行一次迭代女王检查，这至少可以节省分配成本。

就返回完成的电路板结果而言，在失败时使用self或self.board和None的返回值，而不是True和False。

其他几点：

• 由于解决难题不需要状态并且复制木板效率低下，所以我不确定允许__init__方法是否有很多意义。该类非常适合作为分组构造，并且无论该类是静态的还是实例化的，我们都应在EMPTY类内部隐藏诸如QUEEN，Board等静态变量。
• 如果您决定使类保持有状态，则printBoard不应产生side effects-替代__str__。
• 不要hardcode大小的字面量，例如整个代码中的8；这会使班级变得僵化，难以维护并且容易出现错别字和一字不漏的错误。使用len(self.board)代替，并自由提供默认参数。
• fillDiagonal不需要递归。考虑使用列表推导或numpy简化此矩阵遍历逻辑。
• 每个snake_case使用PEP-8变量名称。

这里是重写，实现了以下几点：

class Board:
    EMPTY = 0
    QUEEN = 1
    DIRS = [(x, y) for x in range(-1, 2) 
                   for y in range(-1, 2) if (x, y) != (0, 0)]

    def __init__ (self, size=8):
        self.board = [[Board.EMPTY] * size for _ in range(size)]

    def __str__(self):
        return "\n".join(map(str, self.board))

    def legal_from(self, row, col, dr, dc):
        while row >= 0 and row < len(self.board) and \
              col >= 0 and col < len(self.board[row]):
            if self.board[row][col] != Board.EMPTY:
                return False

            row += dr; col += dc

        return True

    def legal_move(self, row, col):
        return all([self.legal_from(row, col, *d) for d in Board.DIRS])

    def solve(self, row=0):
        if row >= len(self.board): 
            return self

        for col in range(len(self.board[row])):
            if self.legal_move(row, col):
                self.board[row][col] = Board.QUEEN

                if self.solve(row + 1):
                    return self

                self.board[row][col] = Board.EMPTY

if __name__ == "__main__":
    print(Board().solve())
输出：

[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0]