Real number of permutations to the "Drive You Nuts" puzzle?

Question

Over at this post on StackOverflow user Yuval wrote a partial 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. There is only one valid solution.

The OP contends that

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.

So my question is, are there really 7!*(6**7)=~1.4 billion permutations to this puzzle? Can someone better explain to me how there aren't only 6**7=279,936 permutations?

Answer 1

There are far far far fewer possibilities that you have to consider to brute force it.

• Pick one piece for the centre ($7$ options)
• Orient it with the $1$ pointing up
• Pick an order for the other $6$ pieces ($6!$ options)
• Orient each one to match the centre
• Check whether they match around the ring

That's $7! = 5040$ cases. But actually the checks around the ring can be done while generating the permutation around the ring, allowing a lot of short-circuiting.