Twenty-Nine QTM Moves Suffice

I just tried the subgroup (U,U2,U',D,D2,D',B2,L2) and only 32,253 positions remained---but this is still too many. (Of course this group has less symmetry than the ones you mentioned.)

I could simply increase the phase 1 distance (at a rather significant increase in CPU time---perhaps 4x) and that would probably resolve all of these issues. Yes, phase one distance of 17 appears to work, at least for (U,U2,U',D,D2,D',L2,R2)---but at this point, the additional CPU time makes it less attractive.

Thanks, Bruce!

It may well be that my program can work with smaller subgroups, but the changes may be nontrivial.

If the full set of 18 generators is S, and the smaller set of generators defining the subgroups is A, then my program works by finding all sequences of the form b c where b is a sequence of length 16 or fewer from S, and c is a sequence of 4 or fewer from A, and b lies in the requisite coset.

When A is (U,U2,U',D,D2,D',F2,R2,B2,L2), this almost always yields solutions of length 20 or less for all 19B positions. It is rare that it does not, and when it does not, the remaining positions can be solved independently using Kociemba's two-phase algorithm.

I have modified my program to try the smaller group of the two you give (U,U2,U',D,D2,D',L2,R2); in this case, there were 331,094 positions left without solutions of length 20 or fewer over the six cosets required to match the original version of the program. With the larger group of the two, there were 198,494,130 positions left without solutions of length 20 or fewer over the twelve cosets required.

I may be able to work around this with some more effort, such as only solving the even or odd halves of the large coset at any given time. This was suggested to me years ago by Silviu Radu, and would lower the memory requirements to less than 2GB, easily attainable on almost any reasonably modern machine. Testing this indicates that 2,611,616 would remain, so maybe this is not directly viable.

I would like to mention that Herbert Kociemba has made some very significant suggestions towards speeding up my program, so more efficiency may be just around the corner.

So if I just make the simple modifications to work with larger subgroups and thus smaller cosets, I lose much of the advantage of the Kociemba two-phase approach, which typically finds good solutions very easily; too many remaining positions would require separate handling. But there may be a clever trick I am overlooking to help with this.

In reality, the current version of my program requires only about 3.4GB so it will fit in a 4GB machine if the operating system is willing to give a user process that much memory. 64-bit operating systems are becoming quite common, so I suspect targeting 64-bit machines with 6GB of more of RAM (for Windows) or 4GB or more (for Linux) may be the simplest solution.

I am thinking about a coset solver that only requires about 500 MB of RAM, of which about 2/3 for a complete ternary prune table and 1/3 for a binary checklist for coset positions. This is because 500MB is not too much for a background process, and therefore the whole world can help solving the cube. A virus that spreads the coset solver would be optimal. ;-)

The subgroup H I am thinking of contains my favorite subgroup (F2,B2,FB',R2,L2,RL',U2,D2,UD'). The cosets are coded as follows:
- Coordinate one: the three color corner cube (opposite colors are equal) modulo color permutation. There are 153090 three color corner cube positions, so 153090/6 = 25515 positions. You enumerate the positions by fixing a corner that remains the same after each turn, by applying the right color permutation afterwards.
- Coordinate two: an edge coordinate with 2956800 positions, stored as a symrep coordinate with 48 symmetries (Cube explorer has a symrep coordinate with about the same number 63k of representants). Again, this coordinate is based on the three color cube, but the association of edge positions is now somewhat more fancy than just color permutation:
(a) Two positions are the same if you get the second from the first by flipping all eight edges originating from two of the three slices,
(b) Two positions are the same if your get the second from the first by first exchanging two of the three colors and then applying superflip.
Here is what you must do to canonize a three color cube edge position. Say the three color cube has colors red (FB), yellow (UD) and blue (RL). Now look at the UF edge. This edge has two of the three colors red, yellow and blue in some order. Now make this edge red at front and yellow on top by applying (a) and/or (b). The UF edge is now "solved". Next, look at the edges of the UD-slice. Order those four edges any way you like, but fix the ordering. Since the UF-edge is red/yellow, not all edges of the UD-slice can be red/yellow. Now pick the first edge of the UD-slice that is not red/yellow (w.r.t. the ordering). Now make this edge solved as well by applying (a) and (b).

The subgroup is not generated by face turns, but I do not know whether that will frustrate optimizations. At least, I do not see suggestions for such subgroups here. Just an idea. One can add superflip to the subgroup to roughly interchange the sizes of the binary check table and the ternary prune table.

My congratualtion once more in this forum, Tom. I agree with Tom, we should not bother to make the coset solver runnable on 4GB machines. Most people run Windows and without modifications in the boot-process only 2 GB of RAM are allowed for all user processes together. This is definitely not enough to run an effective solver.

In a few years all new machines are 64-bit machine with 12 GB of RAM and here the coset solvers run very effective. In the last months, Tom and I had many discussions how to improve our coset solvers (which are programmed totally independent) on our i7-machines. To solve a whole random coset with about 2*10^10 cubes within 20 moves typically takes for example about 1 minute in the latest version of my solver in HTM - which I think is incredible fast. This speed largely depends on the special structure of the (U,U2,U',D,D2,D',F2,R2,B2,L2) subgroup and we should wait until more machines have the hardware to use such solvers.