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

Question

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

正如"Python语言中的Python算法掌握基本算法"一书中所解释的那样,有一种递归方法.

我们的想法是将电路板分成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

一个人如何培养一种直觉来思考此类问题的解决方案？

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

在这种情况下，2x2 版本很容易解决，但有趣的是它有一个解决方案。

下面是 4x4 解决方案。现在，只要盯着它看一会儿，人们就可能会认出它与 2x2 机箱的连接。每个象限基本上都是2x2 的情况。

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

我发现这个解决方案非常聪明，特别是像他们那样设置偏移线。如果有人可以帮助我理解这一点 [...]

如果展开嵌套循环并将循环变量替换为它们在 中出现的值，可能会更容易理解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表示语句之间的差异。