Generating all unique combinations for "drive ya nuts" puzzle

Question

A while back I wrote a simple python program to brute-force the single solution for the drive ya nuts puzzle.

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?

Answer 1

If there were no piece in the centre, this would be easy. Simply consider only the situations where piece 0 is at the top.

But we can extend that idea to the actual situation. You can consider only the situations where piece i is in the centre, and piece (i+1) % 7 is at the top.

Answer 2

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.

Answer 3

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.