New Results, 13 Moves from Start, Quarter Turn Metric

It took about four months, running around the clock.

The data had to be regenerated from scratch. There is no database, exactly. Rather, the positions are produced in lexicographic order. By producing the positions in lexicographic order, they don't really have to be stored and hence there is no database. The positions are produced in lexicographic order in order to detect and eliminate duplicate positions (those positions that may be produced by more than one sequence of quarter turns).

What did have to be stored were all positions (or really, representatives of all positions, unique up to symmetry) of length 7q or less (7 quarter turns or less). By storing positions of length up to 7q, the program could calculate all positions out to 14q in the same amount of memory. However, calculating out to 14q would have taken about ten times longer, say about forty months. I decided to work on a developing a faster program rather than letting the existing one run that long.

What actually happens is that all positions of length 7q are multiplied by all positions of length 1q, 2q, 3q, 4q, 5q, and 6q and the products are produced in lexicographic order. When duplicate positions are encountered, only one is kept and the shortest possible one is kept. For example, if |x|=7q and |y|=6q, then |xy| might only be 11q rather than 13q. Foe that matter, |xy| might be only 1q.

For that reason, all shorter products have to be recalculated on each run, even if they have been calculated before. On the other hand, the calculation of positions of length 13q took about 90% of the processing time and the calculations of shorter positions took only about 10% of the processing time. The same would be true if I told the program to calculate positions of length 14q. It would still be the case that only about 10% of the processing time would be spent recalculating the shorter positions that were 13q or less.

Jerry Bryan

I would be interested to know the specifications of the machine which did the search (cpu type, speed, memory size etc), and if there was auxiliary storage used.

I had an idea a while back to try to codify a standard 3x3x3 cube position as a number. For example start could be stated as "c3-0". If I'm not mistaken Jaap talks about this on his site as indexing. This could also be a way of searching the cube in parallel on many different computers. Perhaps if one hundred thousand computers with one gigabyte of memory were used in parallel the whole space could be searched in reasonable time.

The tricky part is how to convert the number back into a cube position. We can simply start with C3-0 as start (I will leave off the C3- suffix from now on) and use the position generated from start as U=1, D=2, F=3, B=4, L=5, R=6, U'=7, D'=8, F'=9, B'=10, L'=11, R'=12, etc. Sequences of moves which duplicate positions found so far are skipped over for example U'D is skipped. Now even though there may exist a better way to relate a given cube position to a unique number this does give a catalog of all cube positions in a standardized way.
One could store all the sequences they tried on a DVD and the last number. The next searcher would only have to continue where the other left off so no need to start over again. Unfortunately I don't see any way to do this is parallel but at least we could get away from monopolizing one computer for years and have a start/stop procedure. I wonder how many DVD's it would take to store the whole cube as moves.

Another idea is to use a utility called "par2". The data stored on DVD could have par2 files added to help against data corruption.

2.80 Ghz Pentium 4, Windows/XP, 1GB memory, no disk storage was used. Well, disk was used to make a checkpoint every three or four hours in the event of an electrical failure or a Windows failure. But the checkpoint file on disk had nothing to do with basic algorithm. The actual memory used by the program as it was running was about 300MB.

There are standard ways to convert cube positions to indexes and vice versa. The most typical way is called a Sims table. The way I do it is "Sims-table-like" but it doesn't really use the Sims algoritm.

The idea I use is pretty straightforward. Suppose we have the group S3 acting on the set {0,1,2} rather than the set {1,2,3} as it would be in most group theory books. Suppose we represent elements of S3 in a computer program as vectors of the form [a,b,c], which means 0->a, 1->b, and 2->c. Then, we can list the six elements of S3 in lexicographic order as follows:

[0,1,2] the identity
[0,2,1] (1,2) in cycle notation, swaps 1 and 2
[1,0,2] (0,1) in cycle notation, swaps 0 and 1
[1,2,0] (0,1,2) in cycle notation, vector is rotated left
[2,0,1] (0,2,1) in cycle notation, vector is rotated right
[2,1,0] (0,2) in cycle notation, swaps 0 and 2

If the first digit is 0, you are in the first 1/3 of the table which is the 0-th and 1-st elements. If the first digit is 1, you are in the second 1/3 of the table which is the 2-nd and 3-rd elements. If the first digit is 2, you are in the third 1/3 of the table which is the 4-th and 5-th elements. In the next column, it's a little trickier. For example, if the first digit is 1, then the next digit is either the "first of what is left" (which is 0) or is the "second of what is left" which is 2. The actual calculations are mixed base arithmetic, with the base changing for each column. The net effect is that you write computer code to calculate a bijection that maps S3 to and from the set {0,1,2,3,4,5}. So for example, the vector [2,0,1] maps to 4; and 4 maps to the vector [2,0,1]. Except that the actual calculations in the program must respect the structure of the Cube group, which is not identical to Sn.

Truth is, this particular program doesn't have such a bijection because it doesn't need one. But other of my programs do include such a bijection. But in general, the bijection would be between the set of all cube positions on the one hand, and the numbers from 0 to |G|-1 on the other hand, where |G| is the order of the cube group. Some authors would make the numbers go from 1 to |G|.