棋盘覆盖递归算法背后的直觉是什么？如何更好地制定这种算法？

Question

您可能听说过经典的棋盘覆盖拼图。如何用 L 形瓷砖覆盖缺少一个角方块的棋盘？

如书中所述，有一种递归方法"Python Algorithms Mastering Basic Algorithms in the Python Language."

想法是将棋盘分成 4 个较小的方块，然后将 L 形方块放在较大棋盘的中心，有效地创建 4 个较小的方块，缺少一个方块并通过递归继续。

从概念上讲，很容易理解，但我觉得很难去思考实现。这是一个实施方案 --

    def cover(board, lab=1, top=0, left=0, side=None):
        if side is None: side = len(board)

        # Side length 
        s = side // 2

        # Offsets for outer/inner squares of subboards
        offsets = ((0, -1), (side-1, 0))

        for dy_outer, dy_inner in offsets:
            for dx_outer, dx_inner in offsets:
            # If the outer corner is not set...
                if not board[top+dy_outer][left+dx_outer]:
                # ... label the inner corner: 
                    board[top+s+dy_inner][left+s+dx_inner] = lab


        # Next label: 
        lab += 1
        if s > 1:
            for dy in [0, s]:
                for dx in [0, s]:
                    # Recursive calls, if s is at least 2:
                    lab = cover(board, lab, top+dy, left+dx, s)

        # Return the next available label: 
        return lab

到运行代码，得到如下

    board = [[0]*8 for i in range(8)]
    board[7][7] = -1
    cover(board)
    for row in board:
        print((" %2i"*8)%tuple(row))

    3  3  4  4  8  8  9  9
    3  2  2  4  8  7  7  9
    5  2  6  6 10 10  7 11
    5  5  6  1  1 10 11 11
   13 13 14  1 18 18 19 19
   13 12 14 14 18 17 17 19
   15 12 12 16 20 17 21 21
   15 15 16 16 20 20 21 -1

我花了一些时间才理解这个实现。我不确定我是否完全理解它，尤其是偏移线背后的想法。有人可以尝试简洁地解释实现吗？如何培养直觉来思考解决此类问题的方法？我发现解决方案非常聪明，尤其是像他们那样设置偏移线。如果有人能帮助我理解这一点，或许还有关于如何变得更好的建议，我将不胜感激。

谢谢！

Answer 1

How does one develop an intuition to think about a solution to problems of this type?

该解决方案非常聪明，而且非常针对问题，但它也是一种称为分而治之的更通用的问题解决策略的示例。不要完全攻击问题，而是创建它的较小版本并尝试解决它们，例如。用铅笔和纸，反复试验。看看这些解决方案是否有值得学习的东西。

在这种情况下，2x2 版本求解起来很简单，但值得注意的是它有一个解。

以下是 4x4 的解决方案。现在，在简单地盯着它看了一会儿之后，人们可能会认出它与 2x2 案例的联系。每个象限基本上是 2x2 的情况。

I found the solution very clever, especially setting up the offsets line as they did. If someone could help me understand this [...]

如果您展开嵌套循环并将循环变量替换为它们在 offsets 中出现的值，可能会更容易理解。然后你有四个 if 语句而不是循环。如果没有设置相应的棋盘角方块，则每个语句设置四个中心方块中的一个。

#top left                    
if not board[top][left]:
    board[top+s-1][left+s-1] = lab
#top right    
if not board[top][left+side-1]:
    board[top+s-1][left+s] = lab
#bottom left    
if not board[top+side-1][left]:
    board[top+s][left+s-1] = lab
#bottom right    
if not board[top+side-1][left+side-1]:
    board[top+s][left+s] = lab

作者可能一开始是这样写的，但发现代码重复，转而设计了循环。 offsets 变量表示语句之间的差异。

棋盘覆盖递归算法背后的直觉是什么？如何更好地制定这种算法？

What is the intuition behind the checkerboard covering recursive algorithm and how does one get better at formulating such an algorithm?

python

algorithm

recursion

functional-programming

induction