Making all the unique combinations for the drive ya nuts puzzle

Question

Some time ago I wrote a simple python program to iterate over the only Drive and Nuts puzzle solution.

_{(source: tabbykat.com )}

The puzzle consists of 7 hexagons with numbers 1-6 on them, and all parts must be aligned so that each number is adjacent to the same number in the next part.

The puzzle has ~1.4G non-unique features: you have 7! options for sorting the pieces in order (for example, center=0 , top=1 , continued clockwise ...). After you sort the shapes, you can rotate each shape in 6 ways (each shape is a hexagon), so that you get 6**7 possible rotations for this permutation of 7 shapes. Total: 7!*(6**7)=~1.4G capabilities. 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, since you must divide the total number of possibilities by 6, since each possible solution is equivalent to 5 other solutions (just rotate the entire puzzle by 1/6 turn).

Is there a better way to create only unique features for this puzzle?

Answer 1

To get only unique, valid solutions, you can fix the orientation of the piece in the center. For example, you can assume that the “1” on a piece in the center always points up.

If you have not already done so, you can make your program much more efficient by checking the correct solution after placing each part. After you put the two parts in an invalid way, you do not need to list all the other illegal combinations.

Answer 2

If there was no piece in the center, that would be easy. Just consider only situations where piece 0 is at the top.

But we can extend this idea to a real situation. You can only consider situations where piece i is in the center and piece (i+1) % 7 is at the top.

Answer 3

I think the search space is quite small, although programming may be inconvenient.

We have seven options for the central part. Then we have 6 options for the above, but its orientation is fixed, since its lower edge should correspond to the upper edge of the central part, and also whenever we select a piece to move to the slot, the orientation is fixed.

Other options have less. Let for example, we have chosen the central part and the upper part, as in the picture; then the upper right side must have (clockwise) consecutive edges (5.3) to fit the pieces in place, and only three parts have such a pair of edges (and in fact we have already chosen one of them as the central part )

You can first create a table with a list of parts for each pair of edges, and then for each of the 42 options for the center and vertex continue to move clockwise, selecting only the parts that have the desired pair of edges (to correspond to the central part and the previously placed part) and back off. if there are no such pieces.

I believe that the most common pair of ribs is (1.6), which occurs in 4 parts, the other two pairs of ribs ((6.5) and (5.3)) occur in 3 parts, there are 9 pairs of ribs that occur in two sites, 14 that occur in 1 part and 4 that do not occur at all. Therefore, a very pessimistic estimate of the number of choices we have to make is 7 * 6 * 4 * 3 * 3 * 2 or 3024.