Puzzles

我最近对谜题产生了浓厚的兴趣。在一个夜晚的谈话中，我们开玩笑说，有一个数字谜题是多么酷。这实际上并不是一个疯狂的想法——每个拼图块都需要某种微小的传感器来理解它与其它块的相对位置，并且需要一个微小的数字显示屏来显示图像的一部分。考虑到我们有类似Kindle这样的设备，“长期低功耗图像”技术似乎并不遥远。

块	拼图

有时，你只是感觉格格不入。

但传感器的使用超出了我的预算和当前的知识体系。但没关系，让我们逐步实现。像我通常做的那样，我想将问题分解成更小的部分（寓意）。也许有一个类似的问题我可以解决，这将是一个正确的步骤？一个解决拼图的机器人怎么样？

高级算法

“机器人拼图解决者”意味着我们执行以下操作

1. 我们从单独的图像开始
2. 拼图块被分割。
3. 我们表示了块的特征和边缘。
4. 基于这些特征，分割的块通过算法组合在一起。

但更现实的是，我们想从一个更简单的问题开始

1. 我们从一张完整的图片开始，将其划分为N个方块
2. 根据颜色匹配边缘
3. 我们表示了块的特征和边缘。
4. 基于这些特征，分割的块通过算法组合在一起。

变量

在上面的操作（以及这些是现在的通用注意事项）中，我们需要考虑一些事情。

• 拼图碎片理想情况下应该具有一致的光照，并且所有碎片都应该向上翻转。
• 即使是从顶部向下看，相机也会引入一些倾斜，包括形状和颜色。
• 我们不能对碎片的形状或位置做出任何假设。这意味着虽然我们可以将边缘表示为某种曲线，但一旦引入与假设不兼容的怪异碎片，算法就会崩溃。因此，我们可能考虑一种基于像素的方法。
• 算法可能能够像人类一样解决拼图，也许边缘碎片最容易处理，然后从角落开始工作？
• 我们可以采用递归回溯的方法，从边缘开始，然后从角落向内工作，并根据每个新位置的两个“已决定”边缘选择最可能的碎片。但是，一旦正确碎片的概率低于某个阈值，我们就应该回头。
• 拼图是真实的，因此本质上是不完美的。需要允许一定的误差范围。

应用

虽然这听起来很愚蠢，但机器人拼图解决器有一些有趣的应用。

• 拼图目前是根据拼图块数量进行排名的，但我觉得这并不能很好地表示它们的难度。机器人拼图解决器可以提出一个基于算法的指标，表示难度。
• 有人想过，如果你是色盲，解决拼图的难度会增加多少吗？给定一个难度指标，我们可以看到它如何随着不同变量的去除而变化。例如，如果我们去除颜色，算法会花费更长的时间吗？

拼图解决器

拼图解决器目前可以加载照片，可以进行洗牌，然后重新发现解决方案。我没有在大量图像上测试过，所以效果可能会有所不同，请注意，我仍然认为库处于开发中。您可以在这里或继续阅读以查看基本用法和屏幕截图。笔记本文件位于examples/avocado-puzzle.ipynb，如果您想编辑它。

from puzzles.models import PhotoPuzzle

puzzle = PhotoPuzzle("avocado-halves.jpeg")

# Show the original image
fig = puzzle.get_image_figure()

# Metrics about the puzzle calculated based on minimum piece size we requested

puzzle.metrics()
# Image file         : avocado-halves.jpeg
# Minimum piece size : 30
# Width              : 640
# Height             : 360
# Number pieces      : 252

# Plot the original pieces
fig = puzzle.get_puzzle_figure()

# Shuffle the puzzle and show it
puzzle.shuffle()

# Now show the puzzle broken into pieces!
puzfig = puzzle.get_puzzle_figure()

# Solve the puzzle!
puzzle.solve()

solved_fig = puzzle.get_solved_figure()

这是洗牌后的拼图

然后解决了！

实际上，我发现原始洗牌可能会导致不同的结果（例如，一个不太完美的解决方案）。

变更

如果您想在这里做出贡献，这里有一些想法！

拼图碎片

我希望有一个PuzzlePiece的模型来存储碎片数据，然后以这种方式进行比较。目前我们有一个PlacedPiece，它实际上只是持有数组self.pieces中的索引和一个位置（x,y），这个位置是以棋盘上的坐标表示的。通过某种方式合并这两个会更干净。

图像加载

目前，如果在洗牌之前显示图像，实际上并不完美。但我想应该是这样的（这是一个错误），我们希望能够显示图像，看到它是正确的，然后进行洗牌。