cube files
Indexed Cube Lovers Archive
Symmetries and coset actions (Nintendo Ten Billion Barrel tumbler puzzle)
Submitted by loseyourmarblesblog on Thu, 10/17/2013 - 20:03.
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
UNITED STATES
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
UNITED STATES
