生成“让你抓狂”谜题的所有唯一组合

Question

之前我写了一个简单的Python程序，用来暴力破解这个“让你抓狂”的拼图游戏的唯一解。

_{(来源: tabbykat.com)}

这个拼图由7个六边形组成，上面有数字1到6，所有的拼图块必须排列好，使得每个数字都和下一个拼图块上的相同数字相邻。

这个拼图的可能组合大约有~1.4G种：你可以用7!种方式来排列这些拼图块（比如，center=0，top=1，然后顺时针继续排列...）。在你排列好拼图块后，每个拼图块可以旋转6种方式（因为每个拼图块是六边形），所以对于给定的7个拼图块的排列，你会有6**7种可能的旋转方式。总的可能性是：7!*(6**7)=~1.4G。以下的Python代码可以生成这些可能的解：

def rotations(p):
    for i in range(len(p)):
        yield p[i:] + p[:i]

def permutations(l):
    if len(l)<=1:
        yield l
    else:
        for perm in permutations(l[1:]):
            for i in range(len(perm)+1):
                yield perm[:i] + l[0:1] + perm[i:]

def constructs(l):
    for p in permutations(l):
        for c in product(*(rotations(x) for x in p)):
            yield c

不过要注意，这个拼图实际上只有大约~0.2G个唯一的解，因为你需要把总的可能性除以6，因为每个可能的解都和其他5个解是等价的（只需将整个拼图顺时针旋转1/6圈）。

有没有更好的方法来生成这个拼图的唯一可能解呢？

Answer 1

我觉得这个问题的选择范围其实不大，不过编程可能会有点麻烦。

我们有七个选择作为中心的拼图。然后在它上面，我们有6个选择，但这个拼图的方向是固定的，因为它的底边必须和中心拼图的顶边对齐。类似地，每当我们选择一个拼图放到某个位置时，它的方向也是固定的。

剩下的拼图选择就少了。比如说，如果我们已经选择了中心拼图和上面的拼图，就像图片里那样；那么右上角的拼图必须有（顺时针方向）相邻的边（5,3），这样才能和已经放好的拼图匹配。而实际上，只有三块拼图有这样的边（而且我们已经把其中一块选作中心拼图了）。

我们可以先做一个表，把每对边对应的拼图列出来。然后对于42种中心和上面拼图的选择，顺时针进行选择，只在那些有需要的边对的拼图中选择（以匹配中心拼图和之前放好的拼图），如果没有这样的拼图，就回溯到上一步。

我认为最常见的边对是（1,6），它出现在4块拼图上，另外两个边对（（6,5）和（5,3））出现在3块拼图上，还有9对边出现在2块拼图上，14对边只出现在1块拼图上，4对边根本没有出现。所以，我们最悲观的估计是我们需要做的选择数量是7*6*4*3*3*2，也就是3024。

Answer 2

如果中间没有棋子，那就简单多了。只需要考虑棋子 0 在顶部的情况就行。

不过我们可以把这个想法扩展到实际情况。你可以只考虑棋子 i 在中间的情况，以及棋子 (i+1) % 7 在顶部的情况。

Answer 3

为了得到唯一的有效解法，你可以把中心的那块拼图的方向固定住。比如说，你可以假设中心那块拼图上的“1”总是朝上。

如果你还没有这样做的话，可以通过在每放一块拼图后检查一下是否有效，来让你的程序运行得更高效。一旦你放了两块拼图的方式是错误的，就不需要再去列举其他所有错误的组合了。