Symmetries and coset actions (Nintendo Ten Billion Barrel tumbler puzzle)

Jaap Scherphuis suggested that I post this result here, and it seems very relevant to the discussions taking place about symmetries in Cube solutions.

I recently calculated a solution for the Nintendo Ten Billion barrel puzzle that solves any position within 38 moves. Forgive the chatty presentation there - though there are GAP files linked, there is very little actual mathematics included in that blog post. This would be a more appropriate place to discuss the details. As far as I know, this is the first result of its kind for this puzzle, but I'm very convinced I missed a far better result.

The solution uses a setup stage that reduces the problem from one of 4.5 x 10^12 permutations (A_23, with 3!. 4!^5 . 5! / 2 symmetries) to two smaller problems on A_13 (each with some symmetries due to identically colored balls). The group action on cosets of the symmetry subgroups can be fully calculated to give the "god algorithm" for stages 2 and 3 (3,603,600 and 7,207,200 cosets respectively). This was in fact my first experience coding with GAP.

The result was in fact not what I originally hoped for; I was aiming for a direct descent into subgroups, more like Thistlethwaite. Instead I separated the problem into two almost disjoint subgroups with what feels to me like an "impure" algorithmic first step. I think the reason my original approach failed is quite instructive.

If the subgroup of solution symmetries is H, then any permutation x of the puzzle is in fact the coset Hx, and the (right) group action on cosets is much the same as a descent into a subgroup S in an algorithm like Thistlethwaite's, where the (left) action on xS gives a move sequence that takes us from the entire group G into the subgroup S. (This should not have been so enlightening to me, evidently moving to a subgroup is exactly the same as solving up to the symmetries defined by that subgroup). I was therefore hoping to act in the double coset space HxS. The problem of course is that neither H nor S are normal subgroups (this is the alternating group A_23 after all) and so the 'obvious' group action on double cosets is not well-defined.

I am still persisting, and this initial attempt has given me an insight I never had before, but I would love to hear any suggestions or comments. I am also curious exactly how an issue like this with symmetries seems to be avoidable in the Cube cases, such as the permutations of the center pieces in the 4x4x4. Is it merely a fact that the cube group can be represented as direct products - and as such, does this mean I should not expect similarly strong results in A_n or S_n?

Thanks for listening to a first post by an amateur.

Chris Nash
Hollister, CA

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.


That's quite a result there. I'd somewhat discounted being able to write a feasible optimal solver - I was only reasonably searching to depth 9, and the only pruning heuristic I had was the number of row exchanges needed - treating the plunger up as the 'normal' position, moves with the plunger down are the only moves that change the rows of some balls. Since the plunger up rotations commute (and likewise plunger down) there's around 10^d move sequences of length d - essentially on every plunger switch you can do 8 single-barrel moves, or 16 pairs of two-barrel moves. Suddenly, a depth 8 or 9 search with a table of cosets 8 or 9 positions away seems reasonable... I never expected a number as small as 17. I've been using Jaap's move and position notation, writing T and B for a top and bottom barrel move with the plunger up, lowercase for plunger down (Jaap writes the powers of T as Tr, Trr, Tll, Tl), columns A to E, with A, C, E the long columns, numbered bottom to top. I must admit, I've not been fond of how GAP writes permutations in cycle notation when it comes to state representation - so I've been outputting longhand:
# b   r   y #
# g o k g y #
# b r b o g #
# k y o b r #
# g y k r o #
k for black, roygb arbitrary. b.r.y|gokgy|brbog|kyobr|gykro seems fairly self-explanatory. 17 is still astonishing. I found 22951 cosets at depth 13 solving the 'bottom half' k.k.k|roygb|?o?g?|?????|????? using bottom barrel moves only (obviously there are fewer applicable symmetries with the colors fixed, and only 7,207,200 cosets, 4^13 move sequences).

Move pruning

So T moves and B moves commute, as do t moves and b moves.
But in addition, t and B commute (if I have the move notation
correct), and this helps prune the search space a fair bit.

For a pruning table, just using the position of the black
balls does a fairly good job (you need two "solved" positions,
or else reduce by flip "symmetry").

But my big solver uses a very large hashtable of reachable
positions through depth 11 (think of it like a Bloom filter
but one that returns lower bounds on depths instead of Boolean
existence) so the "average" value returned by the table is
something like 11.9 (more than 85% of the positions in the
hashtable return depth 12). This lets the optimal solver

But all my programs on this could have bugs because they are
brand new, so I'm going to spend some time getting position
input/output and move notation input/output into the programs
and (perhaps, if you are willing) exchange some with you for
checking back and forth.

You published your gap files, and if they have move notation to
perm information I should be able to clarify any remaining
misunderstandings there.

I think I can make my optimal solver about 10x faster without
too much work, and I think I can make a small-memory coset
solver go quite fast, so between the two we should be able to
get a full distance distribution for the puzzle.

I'm happy to share code but I'd much prefer to share ideas and
get separate implementations going so we can compare results
and verify them against each other.


Pruning independently

t and B do indeed commute. Can't believe I missed that :) The gap files do include a "kernel.g" file with all the basic definitions (and a bit of clumsy notation on my part, I tried to be as consistent as I could with permutation notation, so A1 becomes 11, E4 becomes 54 to be integer points in GAP. I didn't stick to that with A5, C5, E5 though).

You're way ahead of me with the pruning. I do have some very coarse pruning tables building now (basically the full coset decompositions to solve 'black and one named color' or 'two named colors'). Range over colors, they're a lower bound, but probably not much good - and certainly not that quick. But they will be independent of yours.

I'm sure my code is buggy too, and I agree about it being better not to share code but independently verify. I'm loseyourmarblesblog at gmail dot com if you'd like to communicate off-list, we're definitely at that stage now! Thanks so much for what is surely going to be a far sharper result than I expected.