4

不久前，我编写了一个简单的 python 程序来暴力破解驱动 ya 坚果难题的单一解决方案。

替代文字
（来源：tabbykat.com）

拼图由 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 圈）。

有没有更好的方法来只为这个谜题生成独特的可能性？

4

3 回答 3

5

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

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

于 2010-04-08T15:39:58.373 回答
3

如果中间没有一块，这将很容易。只需考虑件0在顶部的情况。

但是我们可以将这个想法扩展到实际情况。您可以只考虑棋子i位于中心且棋子(i+1) % 7位于顶部的情况。

于 2010-04-08T15:00:25.673 回答
1

我认为搜索空间很小，尽管编程可能很尴尬。

对于中心部分，我们有七种选择。然后我们有 6 种选择，但它的方向是固定的，因为它的底部边缘必须与中心部分的顶部边缘匹配，同样，每当我们选择一块进入插槽时，方向是固定的。

其余部分的选择较少。例如，假设我们选择了图片中的中心件和顶部件；那么右上角的部分必须有（顺时针）连续的边缘（5,3）以匹配到位的部分，并且只有三个部分有这样一对边缘（实际上我们已经选择了其中一个作为中心部分）。

可以首先建立一个表格，其中包含每个边缘对的棋子列表，然后对于中心和顶部的 42 个选择中的每一个，顺时针进行，仅在具有所需边缘对的棋子中进行选择（以匹配中心棋子和之前放置的棋子），如果没有这样的棋子则回溯。

我认为最常见的一对边是（1,6），出现在 4 件上，另外两个边对（（6,5）和（5,3））出现在 3 件上，有 9 个边对出现在两件，14件出现在一件上，4件根本不出现。所以对我们必须做出的选择数量的一个非常悲观的估计是 7*6*4*3*3*2 或 3024。

于 2010-07-23T18:46:45.263 回答