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

Question

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

如“Python 算法掌握 Python 语言的基本算法”一书中所述，有一种递归方法。

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

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

    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 的情况。

3  3  4  4 
3  2  2  4  
5  2  6  6 
5  5  6 -1  

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

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

#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 变量表示语句之间的差异。