Congratulations, Tom, on the new upper bound for QTM.

Since determining the diameter of the cube group (FTM or QTM) appears to require an enormous amount of CPU time, it seems to me to get to the answer in the shortest possible time, we need to have a SETI-style approach. As I understand it, your program needs over 4GB of RAM (or at least over 3.5 GB), which would seem to severely limit the number of computers out on the internet that would be able to run your program.

So I was thinking, couldn't your program be modified so that instead of being based upon the subgroup <U,D,L2,R2,F2,B2>, couldn't it instead be based upon <U,D,L2,R2> or even <U,D,L2>? Wouldn't that reduce the memory requirements by a factor of 6 or 12 so that the program could run with about 800MB or 400MB, respectively?

It appears to me that since <U,D,L2,R2> and <U,D,L2> are subgroups of <U,D,L2,R2,F2,B2>, that the cosets of these subgroups would simply be separate subsets of cosets of <U,D,L2,R2,F2,B2>. So powerful computers could still process <U,D,L2,R2,F2,B2> cosets directly, while less powerful computers could split the work of processing such cosets.

I realize the symmetry of these other subgroups is less than that of <U,D,L2,R2,F2,B2>, but I think the potential to have many more CPUs working on the problem would more than offset the inefficiencies of using the smaller subgroups.

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.

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.