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
UNITED STATES

Comment viewing options

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

The no flip case

Chris mentioned that the Ten Billion puzzle has a definite top. Perhaps flipping should not be permitted, as you can't put it down right then. With this change, the number of states remains the same, but now you have to potentially get the black balls all the way from the bottom to the top. We wondered, what would be the impact on the diameter? So, I started by making a slight change to my optimal solver (it really was just a few lines of change), and ran a bunch of random positions. I got the following distribution:
 7      3
 8     13
 9     76
10    671
11   4524
12  26532
13 126663
14 415702
15 787010
16 848593
17 449426
18  72713
19    865
Clearly it is more difficult with this change. Immediately we get a lower bound on the diameter of 19.

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

 0            1
 1           13
 2          109
 3          877
 4         7005
 5        55541
 6       435711
 7      3368762
 8     25624253
 9    190560616
10   1358340308
11   8981785980
12  53039005336
13 261494025099
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
l.r.l/llogg/oogyy/yrryb/bgrbo
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.

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!

That's a great result! I don't think it's easy to do a Schreier coset graph analysis based on these results, right, because your "cosets" don't have well-defined "neighbors"?

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

We actually concur; I should have mentioned my counts were cumulative. Here are the non-cumulative counts:
 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

All 467 cosets are now complete.

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         28654
The 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

Have verified the depth distributions out to depth 13. Managed to overheat the laptop with 300 cosets to go, and had to restart those, but either I'd made a really neat optimization or those last cosets were all really easy to get to depth 13, and I finished the calculation overnight.

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!

Great result Tom and well-earned - I'm going to verify the counts out to depth 13, and that's probably taking me longer than it took you to solve the whole thing. (The "trivial" coset was the first one grabbed by one of the cores when I started two days ago, and it's still running).

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

Howdy!

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

I've finished running the coset with all the black balls at the top. The distance distribution is as follows:
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       4755
Since 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

I've also solved the coset with the black balls in the following position (ignore the other colored balls): y.b.l/gobog/lgoyy/lybgo/lrrrr The distance distribution for this coset is
 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      20116
But, 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

Have verified the counts for this coset out to depth 13. Am currently planning to do all the cosets out to depth 13 but I have no idea yet exactly how long that might take; I don't have a whole lot of resources at hand - and the code is still pretty lousy.

Wonderful!

That's wonderful news. If through 13 are right, I can't imagine there are issues with the remaining numbers. (Though you never know.)

You got those results pretty quickly, too. Thanks!

Current bound: 19

In reality, at this point, I've solved 361 of the 467 cosets from positions of
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

With a flip counting as a zero-cost move, and thus we have two positions at depth 0, this is the distance distribution 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 415760941330
Any 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

Can confirm these are both depth 18 positions - of course there are multiple solutions, so I can't match the solution strings. Surprisingly though I did match a good chunk of the beginning and end of the first one:
Tr Br br Trr tll Tl tll Brr bl Bll br Trr tl Tr tll Tll bll Tr
and 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 a lot of fun to hear how others have attacked the problem - thanks so much for sharing! I also got a branching factor of exactly 8.0, by enumerating which moves are allowed to follow the preceding one, and avoiding the commuting pairs. (So there are 12 possible moves after any T move, but only 4 after a B). It surprised me to discover the move sequences ending in a particular symbol end up in the ratios 3,1,2,3 and each multiplies by exactly 8 at each depth. The last move gives me a bitmask of the valid next moves, which I and with another bitmask in another table that says, given the current state (either black only or black plus one color), which next move starts a move sequence that solves this state in the exact move count. And I get a similar figure too... that filter makes the last 6 depth iterations pretty trivial.

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

Puzzle

Howdy!

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

Thanks Tom!

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

The state space is small enough that I wrote an optimal solver and have been running it for a day or two. I've solved over ten million random positions and have yet to find one that can't be solved in 17 moves.

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!

Those look like the same distributions I am getting.

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

Not much new to report from me, other than I've confirmed all these positions are depth 17, and I'm currently scanning adjacent positions - lots of other 17's there, but no new 18's yet.

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

I've now got a rudimentary coset solver running with this method. I still need to index the results properly, and be able to pick up leftovers for an optimal solver, but it performs well enough for me (i.e. about a thousand times slower than Tom's). I ran the coset
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

My numbers were a little more optimistic:
115 3417 61098 654212 1775373 133410
I 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've output my 3417 depth 13 positions, including the move sequences to solve them and the solved state, and shared them here (386121 bytes text). I've done a few cursory checks, such as make sure they're all distinct and in 'canonical' form (colors in abcde order), the solutions are valid patterns, and have verified a few (including a couple of flipped end position ones) in Jaap's javascript app.

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

Happy to be of help, between the three of us, we can get a quorum now :) Looks like it's back to the top of the thread to validate some numbers, but you guys are way ahead of me!

Match these figures

I got 8,580,495 for solving black plus one named color to a named column (the center one), and had a calculation somewhere for solving just that. (I had a couple of others going at one point for two named colors to columns B and D, or A and E). Solving just these is fun and quick, and gives a lower bound for the entire puzzle - which the color degeneracy beautifully wipes out :)

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!

Based on that then I'd like to suggest that the diameter is *probably* 18.

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 105 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

I'm also expecting at most 10^5 depth 18 positions, and that 18 is the limit, but that's more through intuition than anything else, although I've run a few experiments based on Tom's division of the search space based on black ball position 'cosets'. If you 'weigh' a coset by adding the black ball positions in this diagram:
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 "

This is exactly right. The "weighting" you propose matches very closely with what I define as the "hard" cosets.

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?

For fast indexing, the algorithm introduced in jaap's compcube page (http://www.jaapsch.net/puzzles/compindx.htm) works well and can be easily modified to a variety of indexing combinations. But I have no idea how to do fast moves on such indexing without a full move table.
Would you mind sharing your idea?

Probably not as good as rokicki's...

...but Jaap's page gives a few ideas - "split into several indices each with its own small transition table". Obviously the details vary but take his permutation indexing as an example. If you treat the index as a multi-base number, then you can access blocks of consecutive locations with division and modular reduction. So for instance if a move only operates on positions a thru b... then the encoding of the items outside that range does not change. So you can build transition tables for just that range. If a range is of length r, then instead of indexing as n_P_r, index as n_C_r * r! - and then your tables need only update the r! part.

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