生成“drive ya nut”的所有独特组合谜
不久前，我编写了一个简单的 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 圈）。
有没有更好的方法来为这个谜题生成仅独特的可能性？
A while back I wrote a simple python program to brute-force the single solution for the drive ya nuts puzzle.
(source: tabbykat.com)
The puzzle consists of 7 hexagons with the numbers 1-6 on them, and all pieces must be aligned so that each number is adjacent to the same number on the next piece.
The puzzle has ~1.4G non-unique possibilities: you have 7! options to sort the pieces by order (for example, center=0, top=1, continuing in clockwise order...). After you sorted the pieces, you can rotate each piece in 6 ways (each piece is a hexagon), so you get 6**7 possible rotations for a given permutation of the 7 pieces. Totalling: 7!*(6**7)=~1.4G possibilities. The following python code generates these possible solutions:
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
However, note that the puzzle has only ~0.2G unique possible solutions, as you must divide the total number of possibilities by 6 since each possible solution is equivalent to 5 other solutions (simply rotate the entire puzzle by 1/6 a turn).
Is there a better way to generate only the unique possibilities for this puzzle?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
为了仅获得唯一有效的解决方案，您可以将零件的方向固定在中心。例如，您可以假设中心部分上的“1”始终指向“向上”。
如果您还没有这样做，则可以通过在放置每个部件后检查有效的解决方案来提高程序的效率。一旦你以无效的方式放置了两个棋子，你就不需要枚举所有其他的无效组合。
To get only unique valid solutions, you can fix the orientation of the piece in the center. For example, you can assume that that the "1" on the piece in the center is always pointing "up".
If you're not already doing so, you can make your program much more efficient by checking for a valid solution after placing each piece. Once you've placed two pieces in an invalid way, you don't need to enumerate all of the other invalid combinations.
如果中间没有一块，这会很容易。只需考虑片
0位于顶部的情况。但我们可以将这个想法延伸到实际情况中。您只能考虑块
i位于中心、块(i+1) % 7位于顶部的情况。If there were no piece in the centre, this would be easy. Simply consider only the situations where piece
0is at the top.But we can extend that idea to the actual situation. You can consider only the situations where piece
iis in the centre, and piece(i+1) % 7is at the top.我认为搜索空间相当小，尽管编程可能很尴尬。
我们对中心部分有七种选择。那么我们有 6 个选择
其上方的棋子，但其方向是固定的，因为其底部边缘必须与中心棋子的顶部边缘相匹配，同样，每当我们选择将棋子放入槽中时，方向都是固定的。
剩下的部分选择较少。假设对于
例如，我们选择了如图所示的中心部分和顶部部分；那么
右上部分必须具有（顺时针）连续的边缘 (5,3) 以匹配中的部分
位置，并且只有三块具有这样一对边缘（事实上我们已经
选择其中一件作为中心作品）。
人们可以首先建立一个带有列表的表格
每个边缘对的碎片，然后是中心和顶部的 42 个选择中的每一个
顺时针前进，仅在具有所需边缘对的棋子中进行选择（以匹配中心棋子和先前放置的棋子），如果没有这样的棋子，则回溯。
我认为最常见的边对是 (1,6)，它出现在 4 个部件上，另外两个边对（(6,5) 和 (5,3)）出现在 3 个部件上，有 9 个边对出现在两件，14
发生在 1 件和 4 件上的情况根本不会发生。
因此，对我们必须做出的选择数量的非常悲观的估计是
7*6*4*3*3*2 或 3024。
I think the search space is quite small, though the programming might be awkward.
We have seven choices for the centre piece. Then we have 6 choices for the
piece above that but its orientation is fixed, as its bottom edge must match the top edge of the centre piece, and similarly whenever we choose a piece to go in a slot, the orientation is fixed.
There are fewer choices for the remaining pieces. Suppose for
example we had chosen the centre piece and top piece as in the picture; then the
top right piece must have (clockwise) consecutive edges (5,3) to match the pieces in
place, and only three of the pieces have such a pair of edges (and in fact we've already
chosen one of them as the centre piece).
One could first off build a table with a list
of pieces for each edge pair, and then for each of the 42 choices of centre and top
proceed clockwise, choosing only among the pieces that have the required pair of edges (to match the centre piece and the previously placed piece) and backtracking if there are no such pieces.
I reckon the most common pair of edges is (1,6) which occurs on 4 pieces, two other edge pairs ((6,5) and (5,3)) occur on 3 pieces, there are 9 edge pairs that occur on two pieces, 14
that occur on 1 piece and 4 that don't occur at all.
So a very pessimistic estimate of the number of choices we must make is
7*6*4*3*3*2 or 3024.