“self”如何正确更新原始变量？Nqueens问题中的递归/回溯（Python）

Question

这是我的python程序来解决8皇后问题。一切都在工作，除了最后一步打印解决的电路板。我使用递归/回溯来填充电路板，直到找到解决方案。保存解决方案的board对象是self，它是对b1的引用，因此我假设b1，我初始化的原始board，将被更新以包含最终解决的board，并使用printBoard打印解决方案。但是，b1没有被更新，当我出于某种未知的原因打印它时，它持有一个失败的电路板。你知道吗

编辑：在solve中添加placeQueen

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()

                self.placeQueen(col, i)
                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方法中，打印已求解的电路板。简而言之，为什么board的self实例没有更新b1？你知道吗

Answer 1

我不确定它是如何工作的，因为placeQueen从未被调用。因此，我不认为添加一个打印建议提出了一个成品板（我认为它是空的）。[注意：最新更新修复了此问题]

使用受限正方形的思想可以工作，但是这里实现它的方式（没有撤销选项）是低效的；为每个内部循环复制一个全新的Board对象是非常昂贵的。尽管有这么多麻烦，我们还是可以在每次移动时执行一次迭代冲突检查，这样至少可以节省新堆对象的分配和垃圾收集成本。你知道吗

至于返回完成的线路板结果，在失败时使用返回值self或self.board和None，而不是True和False。你知道吗

其他几点：

• 因为解决一个难题不需要状态，而且我们可以（希望）同意复制电路板是低效的，所以我不确定允许__init__方法是否有多大意义。这个类作为一个封装构造很好，我们应该在Board类中隐藏静态变量，比如EMPTY、QUEEN，等等，不管这个类是静态的还是实例化的。你知道吗
• 如果您决定保持类有状态，printBoard不应该产生side effects重写__str__。你知道吗
• 不要在整个代码中hardcode调整文本的大小，比如8；这会使类变得僵硬，难以维护，并且容易出现拼写错误和一个接一个的错误。改用len(self.board)，并自由地提供参数。你知道吗
• fillDiagonal不需要是递归的。考虑使用列表理解或numpy来简化这个矩阵遍历逻辑。你知道吗
• 每个PEP-8使用snake_case变量名和docstrings而不是hashtag注释。如果您觉得必须编写类似# restricts column的注释，请考虑将相关块移动到名为restrict_column(...)的函数中，并跳过注释。你知道吗

下面是实现以下几点的初始重写：

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

    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__":
    for result in [Board(i).solve() for i in range(9)]:
        print(result, "\n")

输出：

[1]

None

None

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

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

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

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

[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]

Answer 2

我相信你的问题与用解题法重新定义自我有关，我甚至不知道你为什么这么做。你知道吗

有关详细信息，请参见此问题：Is it safe to replace a self object by another object of the same type in a method?

像你所做的那样重新分配自我并不是重新分配“b1”参照物。所以当你再次引用b1并做printBoard时，你引用的对象和自行印制板（）”将在完成求解时引用。你知道吗

我会退一步问你自己，为什么你要开始取代自我，这会给你带来什么好处。你可能不需要太多，也不应该这样做。你知道吗