python - 为 "drive ya nuts"拼图生成所有唯一组合

Question

前段时间我写了一个简单的 python 程序来暴力破解驱动器 ya nuts 拼图的单一解决方案。

_{(来源: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 unique 可能的解决方案，因为您必须将可能性的总数除以 6，因为每个可能的解决方案都等同于5 种其他解决方案(只需将整个拼图旋转 1/6 圈)。

有没有更好的方法来为这个谜题生成唯一的可能性？

Answer 1

要仅获得唯一的有效解决方案，您可以将棋子的方向固定在中心。例如，您可以假设中间棋子上的“1”始终指向“上”。

如果您还没有这样做，您可以通过在放置每个棋子后检查有效的解决方案来提高程序的效率。一旦您以无效方式放置了两 block 棋子，就无需枚举所有其他无效组合。