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

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

## Comment viewing options

### Deep Cosets

My coset space of the "no flip" puzzle has 355 cosets at depth 15. I have solved all of these and found no positions at depth 21.

Depth Reduced Elements 15 91,839 126,499 16 3,706,645 5,109,145 17 77,276,103 106,325,962 18 475,834,108 659,075,422 19 110,507,140 162,168,282 20 915 1,565 21 0 0 Sum 667,416,750 932,806,875 355 of 1,716,099 cosets solved

### Great results!

But this makes it fairly certain there are no 21's.

I may run the trivial coset and see what happens there; if the bound is pretty low I may run a handful more cosets and see if I can't get a pretty tight upper bound on the diameter.

### Schreier analysis

I do not know what exactly is involved in a Schreier coset graph analysis and I am not sure the present problem is the place to learn it. The puzzle has cosets on top of cosets.

My cosets are characterized by a particular arrangement of the black tokens and one particular set of colored tokens. There are 8,580,495 such arrangements defining as many cosets. Since one may swap all tokens of one color with all tokens of another color, each distinct state of the puzzle will appear in five of these cosets. So one may cover all distinct states of the puzzle by judiciously solving only one in five cosets. The neighbors of the cosets one chooses to solve are not necessarily in the set of cosets one chooses to solve so in that way the neighbors are not well behaved. Still the neighbors will be in the complete set of 8,580,495 cosets. I would think you could do the Schreier analysis on the unreduced set of cosets.

Could you do a Scheier analysis on the reduced set of cosets if the graph of the reduced cosets were connected? In that case one could get to all the reduced cosets by only considering neighbors which were also members of the reduced set.

### I have made similar changes

I have made similar changes to my coset solver and my results are different from your own:

Depth Reduced Elements 0 1 1 1 11 12 2 84 96 3 657 768 4 5,121 6,128 5 40,007 48,536 6 310,729 380,170 7 2,385,972 2,933,051 8 18,088,623 22,255,491 9 134,226,562 164,936,363 10 951,278,043 1,167,779,692

I have corroborated the above out to depth 8 by a head on breadth first calculation. There are indeed only 12 depth 1 states since Tr = Bl , Trr = Bll , Tl = Br and Tll = Brr due to color degeneracy.

### Concur

0 1 1 12 2 96 3 768 4 6128 5 48536 6 380170 7 2933051 8 22255491 9 164936363 10 1167779692 11 7623445672 12 44057219356 13 208455019763

### Corroboration

Good deal.

I have performed a histogram of 10,000 random positions and the results are similar to yours. And I also find your depth 20 position at depth 20.

10000 States solved, average: 15.43 Depth Count 10 5 11 18 12 101 13 442 14 1555 15 2913 16 3011 17 1691 18 264 Configuration: aba aacdd ccdee ebbex xdbxc Target Depth: 15 16 17 18 19 20 solution: Tr Bl bl Tr Bl tr brr Tl Bll bl Br tll Tl tl br Tr tl Tl tl Tll (20) state: Trr tr Tr tr Tl bl tr Tr trr Bl br Brr Tr bll tl Br Tl br Br Tl (20)

### Diameter is 18

The final distance distribution:

0 2 1 24 2 192 3 1536 4 12256 5 97072 6 760340 7 5866102 8 44510976 9 329872457 10 2335547562 11 15246345702 12 88087946928 13 415760941330 14 1335763735213 15 1993892801539 16 650113766525 17 7682400465 18 28654The final diameter is 18. There are more distance-18's than I expected.

The distribution of coset distances is:

16 27 17 364 18 76

### Have verified the depth distr

The optimization I'd added was to build bitmaps of valid first moves that solve the black balls in a given number of moves, which helped a lot to direct the 'tail' of the searches and reduce the branching factor. Am sure that was pretty obvious to you pro solvers!

### Congratulations!

I think I've got the same sort of performance as Bruce does - one core-hour for each of his cosets to completion, about the same for one of yours to depth 13 only. Gets better with every rewrite, and I've done quite a few by now. Have had a handful of "a-ha!" moments that sped things up, but nowhere near your speeds... I tip my hat to you, sir!

### Kudos

Good work, Tom!

My own coset solver takes on average about an hour to solve a coset to completion, which extrapolates out to on the order of 100 cpu-years to completely enumerate the puzzle positions. Assuming you don't have a network of super computers at your disposal, your techniques are obviously much more sophisticated than my own. I am very impressed.

Bruce M

### Supercomputers

Actually, I think using larger cosets makes it a lot faster. The pattern database/pruning table used to guide the search is trivially small so it easily fits in cache. I run the coset until there are (in this case) 32,768 positions left (about one in 75,000), so the "hard/deep" positions are solved separately.

And the four machines I used are quite speedy.

Each 2.5B-sized coset took about one-half CPU-core-day to run until there were 32768 positions left, and a negligible amount of time to solve the remainders. Indeed, if I had run them until there were, say, 250K positions left each, it's possible things would have gone a lot faster, but I didn't want to use that much disk space (to store the leftover positions). Then again, the leftover positions only needed to be stored for a short time.

The trivial coset took a long time to run; I should have separated this one out and done it separately and at least for this one massively increased the number of leftover positions.

Overall, I think this could probably have been solved even more quickly just using a standard full-state exploration and disk files. But breaking it into cosets and solving them separately lets me check a lot more intermediate results, lets me distribute it over multiple machines, and is more easily restartable in the case of "events".

### Estimates

The one thing I have not implemented is to shuttle off the the higher depth coset elements to a dedicated solver. I think doing so might get the time per coset down to about 5 minutes. This would get the time for a complete solution down to about 12 cpu-years. The main bottleneck in my solver is testing potential solutions, which requires a lot of processing as I have it written. I might be able to speed things up significantly there. Still, I doubt that I could get the time down to a few cpu(core)-weeks as you have done. Again, well done.

### "Trivial" coset solved---new bound = 26

0 1 1 8 2 48 3 320 4 2036 5 12998 6 81664 7 499519 8 2969817 9 16455617 10 70060785 11 152012945 12 402532837 13 1160072887 14 713410959 15 28051429 16 4755Since solving the black balls never takes more than 10 moves (and maybe a flip), this reduces the upper bound on the diameter from 38 to 26. The worst case to get all the black balls to the top is when all the black balls are in the middle of the five-high columns. Of course we strongly suspect it is only 18, but this is still progress.

### A different coset---upper bound now 23

0 0 1 0 2 0 3 0 4 0 5 0 6 8 7 144 8 1966 9 22714 10 237295 11 2287899 12 20062339 13 149219087 14 796100070 15 1420180407 16 158036580 17 20116But, it never takes more than six moves from any position of the black balls to attain the black ball position from this coset (or its flipped cousin). This lowers the upper bound to 17+6 or 23.

### Have verified the counts for

### Current bound: 19

the black balls (467 unique with respect to flips and mirrors, that is).

Of these, 12 had distance 16, 287 had distance 17, and 62 had distance 18.

Every coset is within a distance of one of one of the solved cosets, so this

makes the current upper bound 19.

There are only six remaining cosets that might possibly have a distance-19

position; I hope to have these all solved by tomorrow sometime, and the

rest shortly thereafter, at which point every position will be solved, and all

the distance-18 positions listed.

### Distance through depth 13

0 2 1 24 2 192 3 1536 4 12256 5 97072 6 760340 7 5866102 8 44510976 9 329872457 10 2335547562 11 15246345702 12 88087946928 13 415760941330Any confirmation of any of these values appreciated. -tom

### Test Results

With a refurbished "Path Iterator" my coset solver appears to be giving good numbers. A full enumeration of the cosets out to depth 10 matches Toms numbers and an enumeration of Chris's test coset matches his numbers.

Barrel Puzzle Enumerator Sequential coset iteration Enumeration to depth: 10 Snapshot: Sunday, November 10, 2013 at 10:30:40 AM Central Standard Time Depth Reduced Elements 0 1 2 1 18 24 2 157 192 3 1,193 1,536 4 9,252 12,256 5 72,355 97,072 6 562,190 760,340 7 4,312,970 5,866,102 8 32,643,340 44,510,976 9 241,919,502 329,872,457 10 1,714,122,564 2,335,547,562 1,716,099 of 1,716,099 cosets solved

Barrel Coset Solver Client Cosets solved since launch: 1 Average time per coset: 0:21:53.476 Server Status: Barrel Puzzle Enumerator Solving coset for representative element: aba axabb bcccc xxddd deeee Snapshot: Sunday, November 10, 2013 at 12:03:00 PM Central Standard Time Depth Reduced Elements 0 0 0 1 0 0 2 0 0 3 0 0 4 0 0 5 0 0 6 0 0 7 0 0 8 0 0 9 0 0 10 0 0 11 0 0 12 115 115 13 3,417 3,417 14 61,098 61,098 15 654,212 654,212 16 1,775,373 1,775,373 17 133,410 133,410 18 0 0 Sum 2,627,625 2,627,625 1 of 1,716,099 cosets solved

### Antipodes

I left my coset solver running overnight and it kicked out a couple depth 18 positions. I'm still not completely confident I have the bugs out of my solver after fumbling the port of my path iterator. Would someone be so kind as to confirm these results?

Configuration: abx acadc acdbc ebxdd ebexe Target Depth: 11 12 13 14 15 16 17 18 solution: Tr Br br Trr Brr tll Tl bl Bll br tll Trr tl Tr tll Tll bll Tr (18) state: Tl brr Trr trr Tl tr Tll trr bl Brr br Tr trr Bll Tll bl Bl Tl (18) Configuration: abx ababc addbc edxdc ecexe Target Depth: 11 12 13 14 15 16 17 18 solution: Tr tl Tr tl bl Brr bll Brr br Tl tr bl Trr brr Bl bl Bl Trr (18)* state: brr tl Tl tl Trr brr Tl Br bl Tr trr Tll trr Tl Bl br Bl br (18)

### Can confirm these are both de

Tr Br br Trr tll Tl tll Brr bl Bll br Trr tl Tr tll Tll bll Trand even more with commuting moves (TB, tb, and tB). My path iterator never outputs BT, bt or Bt. Looks like you made a different choice ;)

### Alternate Solutions

The first solution found is dependent on the enumeration of the generators. In my code:

enum PM_move {Tr, Tl, Br, Bl, tr, tl, br, bl, Trr, Tll, Brr ,Bll, trr, tll, brr, bll, PM_move_max};

So solutions out of my solver are more likely to start with Tr or Tl and are less likely to start with brr or bll since Tr starts the first branch of the search tree and bll starts the last branch. Which commuting pair of moves is used is also dependent on this order as the first pair formed in a systematic formation of all binary pairs is the one used. So (Tr Br) not (Br Tr) but (Br tr) not (tr Br). This is a consequence of how I generate move sequences.

In the initialization of my PathIterator class I do a breadth first expansion of the search tree and produce a database containing an optimal path for all unique positions out to depth 6. This database is in the form of a linked list of moves. The nodes at depth 6 are then linked back to the nodes at depth 3 such that the depth 5 + depth 6 moves match the depth 1 + depth 2 moves leading to the depth 3 node. In this way the iterator produces move sequences greater than 6 in length by dovetailing two or more move sequences of length 6 and less. With this I can produce move sequences out to an arbitrary depth avoiding length 6 and under redundant move sequences. The iterator's branching factor for the Barrel puzzle is right at 8.0. This only slighter higher than the optimum out to depths at which the high end pruning table supercedes.

### It's a lot of fun to hear how

It's great to know that we've all made different approaches and managed to cross-check the results so successfully.

### Puzzle

I wish I could say I had some answers to your questions, but at the moment I don't.

But some questions, because this seems like a cool puzzle to work with.

Does flipping the whole puzzle over count as a move?

Thanks!

-tom

### Flipping

I treated flipping the puzzle over as a valid operation, but with zero cost in the move count. In the algorithm I just use this as an initial step (basically choose the end with the most black balls as the end the black balls will be in the solution).

The operation "flip the puzzle and reverse the plunger" (to keep the position notation) is an involution and an odd permutation - so that takes us from A_23 to S_23 - but then the solution symmetries will likewise include odd permutations.

If I write F for this flip operation, though, as an 'external' symmetry of the puzzle, the basic moves T, B, t, b (top and bottom barrel, plunger up or down) are conjugated by F = F^-1:

F T F = b^-1 and F B F = t^-1

so any solution that uses F can push the F through so there's at most 1 F in the solution, and it doesn't seem worth counting as a move.

Jaap's javascript version allows either orientation (and any color permutation), so if I output a solution for there and it uses a flip, I just conjugate all the moves.

### Optimal solver

That leads me to believe that exploring the entire state space with a coset solver will be quite practical. I may attempt to do so over the next few days.

With flip being "free" and with left-right symmetry, there's another reduction of 4 in the "state space" so we're talking about roughly 1e12 states. I plan to run a coset solver through depth 16 and much of depth 17, and do "leftover" positions with a fast optimal solver.

The "subgroup" I will use will be the positions of the black balls; there are probably fewer than 500 such after reducing by symmetry. Each coset (loosely speaking) will then be of size about 2.5B entries.

I believe I have worked out how to do the necessary fast indexing and moves; I just need to write the code.

It would be great if we can agree on a move representation and a state representation so we can share sequences and positions.

-tom

### Optimal Solver

Tom

I've knocked together an optimal solver for this "Barrel" puzzle and solved a set of 10,000 random positions:

10000 States solved, average: 14.58 Depth Count 9 1 10 5 11 38 12 189 13 955 14 2959 15 4418 16 1414 17 21 Depth 17 Elements br Tl tl bl Tll Brr brr Tll bl Tll Brr tl Tr tll bl Br br Tr brr Tr trr Tr tr Trr Bl bll Tll Br bl Bl bl Tl tl Tl br Bll tr Tll bl Brr bll trr Tl tl Tll Bl bl Bl bl Br Tl brr Brr brr Bl brr tl Tl brr tl Tl tl Tr bl Bll bl Br Tr trr Bl Tr bll tr Tr trr Tr trr Br bl Bll Tll brr tll Bl Tl tll Tll br Tr brr tl Tll bll Tll bll Bl brr Bll br tr Br Tl bll tr Tr tr Trr Bl br Tll Br bl Bl br Brr tr Trr bll Tl bl Bl brr tr Tr tr Tr brr Br br Brr Tl tll bl Trr Bl br brr Trr Br br Tr tr Tl Bl brr tl Tr br Br brr Bll tr br trr Tll trr Bll Tr br Br Tl bll Brr bl Brr Tr tr Trr tl Tl tll Tr tll br Br bl Tll tr Tll bll Bll br Br brr Br tr br tl Tr bl Br tr br Tl tll brr Tll Bll br Br brr Bll tr br br Tl tl Tl Br bl Br bll tl Tl br Tl trr Bl br Br br br Bl brr tr Trr tll Tr brr Br bl Tl Bl br Tl tl Tl tr tll Tll trr Tll br Tl tll Tr brr Trr Bl brr Tll trr bl Br Tl brr Tll Bl brr Brr trr brr Tl tr Tr trr Bl br Br brr Tl br bl Tr tll Trr bll Br brr tll Bl bl Tll bl Tll trr bl Bl Tl tl Tll bl Brr tl Trr bll Tl tll Tl bll Br br Bl br tr Tr Tll br tr Tr tll Tl tl Tr trr bl Bll Tll br Bl brr Bll Tl tl Tr tr Tl bll tl Tr brr Br bll Tll br Tll tll Bll bl Tl br Brr Tl bll Br bll tr Tll br Tl tr Tr bl Bl br tr Tl

How does the above distribution compare with what you're seeing? I think I've got the bugs out of my solver but I'd find it reassuring if my results compare well with yours. And could you solve a few of the above depth 17 states and confirm that they are actually at depth 17? The move sequences applied to the puzzle solved with the plunger in up position give the correct states. If you're not set up for input as move sequences here are the first four as permutations on the following grid:

Token Grid 0 1 2 3 7 11 15 19 4 8 12 16 20 5 9 13 17 21 6 10 14 18 22 {7,11,16,19,4,9,6,15,12,10,3,0,14,5,13,17,1,8,2,21,20,18,22} {8,4,1,20,0,22,13,9,12,18,17,15,19,16,2,7,10,11,21,14,3,5,6} {8,16,19,7,20,21,18,15,17,3,12,9,0,5,1,2,6,4,13,10,22,11,14} {17,1,16,7,18,21,14,15,20,12,22,11,2,4,6,3,13,5,10,19,8,9,0}

### Howdy!

I will test things tonight but it looks good. (I don't

yet parse or generate move sequences, but that's easy to

add; I do parse and generate positions).

Here's a test position I'd like you to check; I see this

as distance-18 (but I don't want to *announce* it as such

without separate confirmation):

l.b.l/glglg/rrbrg/oryoy/oybyo

Thanks for participating! I'm making good progress but still

have some more code to write and so little time to write it in.

-tom

### Standard Configuration Strings

I'd like to propose a standard for Barrel puzzle configuration strings. In this standard the letter, x, would stand for the three normally black tokens and the letters, a thru e, would stand for the other five colors which may be assigned in an arbitrary manner. The colors are listed by row from the top to the bottom. Under this convention a solved tableau may be represented as:

xxx abcde abcde abcde abcde

and my list of depth 17 positions may be represented as:

bcd edxde accxe bbabd aacxe bax ebdbc xceba eddca cdxea bde bdbxb edxae eaaac dcxcc dxd bdcae dexcb ecaab ceabx axb cdcca dadxb bdeca xbeee xdb eebab ddxec ccaca bedax bxb aedde eaxae dcdca cbxcb ebx dcabb ddcec bxaee aacdx xcb aacdc axdde abcbe bedex ddx acada becdx bcebe xcaeb dbe xcaxb abcee dadbd ecxca axd cbbdd bxebe cacdc eeaax ddb ecexx deeca abaab ccxdb bax cbbbc xdede accde xedaa exx bbabb ceacd ecdcd adxae cxc eadad edead bxxbe cacbb dxa bdbca xdcba ecxdb caeee exd bdbab aeaex aecdb cdxcc exb caadd bbcxa eddba eeccx cxb beabc xadca daeec beddx xbb eddec dbxcb adaec axeac

### Confirmed

### Thank you. My confidence is

Thank you. My confidence is growing that the solver is not missing some lower depth solutions though some bug or error of logic .

I'm now working on a coset solver for solving cosets of the subgroup having the black tokens and one color solved. This affords 8,580,495 cosets of 525,525 elements. Using right/left and upside-down symmetry the number of cosets one actually has to solve reduces to 2,146,575 if I have done the symmetry reduction correctly. I'm currently trying to put together a scheme to index the the elements of a coset. I have a good idea how to do it—I just need to write the code. I should have the coset solver up and running before too long. I doubt if it will be fast enough to enumerate the puzzle positions completely—at least not with the resources I have at hand. We'll see.

### Whoops

I now find that I have incorrectly counted the cosets by not correctly handling the color degeneracy. There are one fifth the number of cosets with five times the number of elements. So there are 1,716,099 cosets of 2,627,625 elements. The color degeneracy wipes out much of the symmetry reduction. The number of symmetry distinct cosets only reduces to 1,323,041 under right/left and upside-down symmetry. I'm finding this puzzle quite an interesting challenge to model.

cosets = 23! / (16! * 3! * 4! * 5) = 1,716,099 elements = 16! / (4!)^5 = 2,627,625

### It's not just the symmetry

a?a axa?? ????? xx??? ?????to completion, your single color solve pruning table gives a lower bound of 12, flipped or not. Lots of 17's. No 18. I'd be happy to check results off list if you wish (my board username at gmail dot com). Using the first colored ball as the discriminant for color degeneracy kills not only the symmetry but a lot of the coset adjacency too. (We're in the original 'double cosets of not normal subgroups' territory of my original post, the color degeneracy symmetry means the 16 images of the coset under a single move are not well-defined). There's some neighboring but not as much as we'd like, and a proof this way would take a lot of the 1,323,041 uniques to be solved.

I believe I'm at my limits of mathematics, coding, and available computation resources now, and I'd like to thank everyone who viewed and commented on this thread for what has been a great learning experience for me. I believe the result is just around the corner...

### Coset solved

I input your coset into my coset solver, which is very much in the testing stage:

2013-11-07 15:41:26.418 BarrelClient[20202:303] 12 115 2013-11-07 15:41:26.453 BarrelClient[20202:303] 13 3340 2013-11-07 15:41:27.030 BarrelClient[20202:303] 14 59361 2013-11-07 15:41:35.894 BarrelClient[20202:303] 15 639610 2013-11-07 15:43:28.267 BarrelClient[20202:303] 16 1782902 2013-11-07 16:01:34.381 BarrelClient[20202:303] 17 142297 2013-11-07 16:01:34.381 BarrelClient[20202:303] Coset Complete

Do these numbers look anywhere near correct?"

### My numbers were a little more

115 3417 61098 654212 1775373 133410I went through those 13's and check with the optimal solver; came out the same here. (That just proves I'm consistent with me, nothing else).

### Incorrect Counts

I have solved a big chunk of my depth 14 states and found none at the wrong depth.

Well, either you or I or both of us have something wrong. As my former boss used to say when a reaction would take off and end up dripping from the ceiling: "Well, we're learning." The indexing of the coset elements is tricky what with color degeneracy and such. I am by no means sure I'm doing it correctly. I could be coming up with the same index for two states which should be different. Could be coming up with two different indexes for two states which should be the same. This might show up as incorrect counts although the depth of the states is correct.

Now, what I need to do is finish up, get my client application hooked up to my server application, do a partial enumeration and see if the numbers match up with Tom's.

### I've output my 3417 depth 13

I'm intrigued by this mismatch, a lot, but I think burden of proof is on me for having more shorter solutions than longer ones. They shouldn't keep an optimal solver busy for too long, and of course I'd be thrilled to find out which of these I got wrong. No doubt the indexing is tricky, and I'm absolutely certain there are at least three different approaches being used here...

### My Bad

I extracted the positions on your list not on mine and found that my solver reports non-optimal solutions for them. The fault is my "path iterator" which is designed to efficient walk through the search tree. I did a quick hack of the iterator to dumbly walk through all 16^n move sequences. Makes the coset solver slow as molasses but it now gives numbers in accord with yours.

2013-11-08 22:56:47.999 BarrelClient[3628:303] aba axacd bbecd xxecd beecd 2013-11-08 22:56:50.975 BarrelClient[3628:303] 12 115 2013-11-08 22:56:51.957 BarrelClient[3628:303] 13 3417 2013-11-08 22:57:42.992 BarrelClient[3628:303] 14 61098 2013-11-08 23:31:47.943 BarrelClient[3628:303] 15 654212

### I'm missing solutions

I did an enumeration out to depth 10 on all cosets this morning and my numbers do not match Tom's numbers. To confirm I did a head on breadth first search of the search tree out to depth seven and found the same number of states for each depth as Tom. My coset solver is missing some solutions. Your list of solutions should be very useful in tracking down the bug. I can look at the solutions I'm missing and see why I'm not catching them.

Thanks!

### Happy to be of help, between

### Match these figures

It does back up the intuitive notions of what makes a position hard to solve, though. Vertical movement is costly, so difficult positions have the black 'center of mass' at the middle, and each color 'center of mass' towards the ends. Positions like that can take quite some moves even to solve a single color.

### Color degeneracy

My optimal solver uses a pruning table which lists the depths of all arrangements of the black tokens and one set of colored tokens. This gives 23! / (16! * 3! * 4!) arrangements:

2013-11-05 16:14:53.253 Barrel[1443:549b] 0 5 2013-11-05 16:14:53.387 Barrel[1443:549b] 1 58 2013-11-05 16:14:53.516 Barrel[1443:549b] 2 428 2013-11-05 16:14:53.641 Barrel[1443:549b] 3 2718 2013-11-05 16:14:53.766 Barrel[1443:549b] 4 14183 2013-11-05 16:14:53.895 Barrel[1443:549b] 5 62060 2013-11-05 16:14:54.039 Barrel[1443:549b] 6 223053 2013-11-05 16:14:54.218 Barrel[1443:549b] 7 649371 2013-11-05 16:14:54.443 Barrel[1443:549b] 8 1303368 2013-11-05 16:14:54.697 Barrel[1443:549b] 9 1794771 2013-11-05 16:14:54.956 Barrel[1443:549b] 10 2006085 2013-11-05 16:14:55.179 Barrel[1443:549b] 11 1553772 2013-11-05 16:14:55.352 Barrel[1443:549b] 12 785668 2013-11-05 16:14:55.486 Barrel[1443:549b] 13 176054 2013-11-05 16:14:55.609 Barrel[1443:549b] 14 8352 2013-11-05 16:14:55.730 Barrel[1443:549b] 15 549 2013-11-05 16:14:55.731 Barrel[1443:549b] Total: 8580495

If one uses these 8,580,495 arrangements to define the cosets of a coset solver one ends up solving each puzzle position five times due to color degeneracy. The expedient I am using to eliminate this redundancy is to only solve the cosets defined by arrangements where the first colored token is in the first slot not occupied by a black token.

### Depth 18 confirmed

I also find the position at depth 18:

Target Depth: 12 13 14 15 16 17 18 Tr Br bl Bl bl Bl trr Tr tr Tll trr brr Bll bll Tl br Brr tll (18) (solution) trr Bll bl Tr brr Brr bll tll Trr tl Tl tll Br br Br br Bl Tl inv(18) (state)

We're lookin' good.

### Great!

I've run coset solvers far enough to identify what are likely the "hardest" cosets (the ones with the highest average move count).

I've run the single hardest one through to depth 17, and out of 2.5B positions, only *32* were found that are at a distance greater than 17.

I've run tens of millions of random positions, and found no distance-18 or greater positions in those runs.

This is not a proof, of course, and my programs need to be vetted and their results duplicated, but this is what I'm seeing.

If there's a distance-19 position, it's hiding well.

### Depth 19 positions?

I don't know. Even if the probability of finding a depth 18 position is 10^{-8} that still
gives 10^{5} depth 18 positions. I think a few outlying depth 19 positions might
well exist. Who knows? I find it amazing that there are no depth 21 cube positions in f-turn metric and that
there is a depth 26 position in the q-turn metric.

### Concur with estimates

0 . 0 . 0 2 1 2 1 2 4 3 4 3 4 6 5 6 5 6 8 7 8 7 8(by the way, this diagram looks much better with the plunger halfway down!) - then each black ball layout has a weight from 0 to 12. (Flip the puzzle subtracts the weight from 24). My guess is the depth 18 (or higher, but I expect not) positions are concentrated in the high weight cosets. I'll consider a coset 'solved' if all its depth 18 positions are listed, and 'verified' if we know its diameter is at most 18 (but we may not know the depth 18 positions). Cosets are neighbors if one of the 16 moves takes you from one to the other. Once a coset is solved, all its neighbors can be verified by checking just the images of the depth 18 positions under the neighbor moves. I'm working on a solution strategy now. If we suppose all cosets below a given weight have a diameter of 17, then it appears we have to 'solve' surprisingly few in order to 'verify' them all. Numbers soon... but I really need to write some faster solver code.

### This is exactly right. The "

Your "verified" essentially means we know the "distance" of the coset (the greatest distance of all the positions in that coset).

I expect most cosets have a distance of 17, and thus to show the diameter we only need solve a subset of the cosets.

We have some good idea (based on a partial coset search) of how difficult each coset will be to solve, and we have full information of its neighbors, so we should be able to find a minimum-difficulty subset of cosets to solve.

Should we hit some unexpected distance-18 positions, we can simply solve a few more neighbors.

Another approach worth doing is an in-memory full search; this will take on the order of 160GB of RAM, I believe. It is easily parallelizable as well. And this approach will give us full information about all positions.

### how to do fast moves on such indexing?

Would you mind sharing your idea?

### Probably not as good as rokicki's...

Obviously some details are needed if a move acts on multiple ranges, but it can all be done with reasonable tables.

## The no flip case

Next, I changed my coset solver in the same way, and computed number of positions through depth 13:

I hope someone can verify some of these numbers. Based on this, I found what looked to be the hardest coset (with the fewest found positions at depth 13) and solved it to completion. This led me to find quite a few distance-20 positions, including This increases the lower bound to 20. It's not impossible there are some distance-21 positions, so I will probably run a few additional cosets just to see.It's interesting to me that the upper bound does not seem to have increased by much.