6

您可能听说过经典的棋盘覆盖拼图。您如何使用 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

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

谢谢！

4

1 回答 1

2

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

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

在这种情况下，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变量表示语句之间的差异。

于 2015-05-26T15:41:07.737 回答