为“驱动你的坚果”拼图生成所有独特的组合

不久前,我编写了一个简单的python程序,用于暴力破解drive-ya nuts难题的单一解决方案。

alt text http://www.tabbykat.com/Drive%20ya%20Nuts%20Travel%20Sol%20c.jpg

拼图由7个六边形组成,每个六边形上的数字为1-6,所有的棋子必须对齐,以便每个数字与下一个棋子上的相同数字相邻。

谜题有 ~1.4G 非独特的可能性:你有 7! 按顺序排序的选项(例如, center=0 , top=1 ,按顺时针顺序继续…)。在你把这些零件分类后,你可以用6种方式旋转每一个零件(每个零件都是六边形),这样你就可以得到 6**7 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圈)。

有更好的方法产生 只有独特的可能性 为了这个拼图?