God's Algorithm for the Rubik's Cube Upper Face

#### Problem

What is the shortest number of face turn moves to solve all Upper face positions of the Rubik's Cube?

16.

The result has been found by computer analysis. 16 twists is all it takes to be able to solve any Upper face configuration. The rest of this document looks at the implementation, tricks to speed-up calculations and the results. The Singmaster cube notation (Front, Upper, Right, Left, Down, Back or FURLDB) is used.

Solving the Upper face is much easier if you start with the initial configuration and try and find the moves necessary to reach all possible positions on the Upper face. This is the approach used.

My result is for face turns only. I did not calculate for quarter turns, though it should be possible to use the same approach and calculate the answer.

See here for the updates to the table in my book "How to Solve the Cube in 37 Seconds".

#### My History With This Problem

In 1981-1982 (I think mostly 1982), I wrote a computer program to help find the shortest moves to solve the Upper face. The program was written in Basic on an Apple ][. From memory, I think my Apple had 48K or RAM. I think 16K was used by the operating system/basic interpreter leaving only 32K for applications. Again, from memory, I think the version of Basic I had did not allow recursion. The CPU ran at 1Mhz. I had a floppy drive that could store an addition 128K.

My algorithm was to combine any move that only affect the Upper face with all variants (e.g. rotations, mirrors) of the move. I spent hours on writing the program and feeding it the data. The software would run for days. It relied heavily on the various symmetries of the Upper face positions. Eventually I could do any Upper face move in 21 face turns. David Singmaster mentioned this in Cubic Circular, Issue 5

I printed out the results and stored them. Twenty five years later, I came across the old print outs and was curious how much I could improve on my original work.

Both my maths and computing skills had changed since then. Probably one for the better and one for the worse.

#### Size of Problem

There are 4 Upper face corners and 4 Upper face edges. There are 4!=24 unique possible positions for the Upper face corners. Similarly with the edges. However, it is impossible to swap just two corners (and leave the rest of the cube in its initial configuration). If you swap two corner, two edges are also switched. Therefore the number of positions must be divided by two. There are 3^3 possible corner twists. Once the state of three of the corners is known, the other twist is fixed. It is impossible to twist one corner without twisting another. Similarly, there are 2^3 possible edge twists. It is impossible to twist one edge without twisting another. The total number of states (ignoring symmetry) is:

``````
4! . 4! . (3 ^ 3) . (2 ^ 3)    24.24.27.8
--------------------------- =  ---------- = 62,208
2                      2
``````

There are 62,208 possible configurations of the Upper face (with the rest of the cube in its initial configuration). Many of these configurations are rotations or mirrors or inverses of each other. For simplicity, we ignore the various symmetries.

#### Implementation

I decided on the basic design on the way home from a long car journey and also the various improvements that I knew would be needed. I was curious how long it would take to find God's Algortihm for the Upper face (the shortest possible set of all moves) or even if it would be possible to find it.

As is my custom, I didn't bother with any Internet search to find out if anyone had already solved the problem.

I have access to two Linux machines (2.0Ghz processor, 512Mb RAM) and a Mac Powerbook (1Ghz processor, 1Gb RAM) Within a couple of hours, I had a very simple recursive algorithm written in C. I compiled and tested on both machines. The Linux machines were faster than the Powerbook so were the primary machines I used.

My 1981/82 algorithm was written in Basic. I used an array to hold the color of each of the 48 facelets and updated this array any time a face was turned. Clearly, this is not the most efficient algorithm.

For my current algorithm I decided to use 4 separate arrays to hold the corner positions, corner twists (orientations), edge positions and edge twists. I decided to use the word twist, and not orientation, because it was easier writing code with the letter 't' and not the letter 'o' (which looks too much like a zero '0'). As I was using C, the array numbers started at 0. I used global variables (without testing, I decided that global variables would be quicker than passing variables on the stack). I assigned the array names, gcp, gct, gep, get for the corner positions, corner twists, edge positions and edge twists respectively. Arbitrarily, I assigned the following positions for the corners: UFL=0 ULB=1 UBR=2 URF=3 DLF=4 DBL=5 DRB=6 DFR=7 and for the edges: UL=0 UB=1 UR=2 UF=3 FL=4 BL=5 BR=6 FR=7 DL=8 DB=9 DR=10 DF=11

Most of my cubes have the green face opposite the blue face. Assuming this coloring scheme, I set up green as the Upper face and blue as the Down face. Each corner therefore has either a blue or green facelet. For twists, I looked at the position of the green or blue facelet. If the blue or green facelet was on the Upper (or Down) face, then I assigned this a twist value of 0. If the blue or green was on the clockwise rotation of the corner (assume looking from outside the cube on a line through the corner to the center of the cube) then I assigned this a twist value of 1. If on the anti-clockwise turn, I assigned it a twist value of 2. Moving the Upper or Down face does not change the twist values. Moving the Left face clockwise causes the corner at position 0 to hold the corner that was at position 1 and changes twist. My code for moving the corners one turn clockwise on the Left face is:

``````
// New corner positions
k = gcp[0]; gcp[0] = gcp[1]; gcp[1] = gcp[5]; gcp[5] = gcp[4]; gcp[4] = k;
// New corner twists
k = gct[0];
gct[0] = (gct[1] + 1) % 3;
gct[1] = (gct[5] + 2) % 3;
gct[5] = (gct[4] + 1) % 3;
gct[4] = (k      + 2) % 3;
``````

In what was the first of many speed improvements, I found it faster to use an array that contained the value of the modulus three arithmetic. The actual implemented code is

``````
int p1mod3[] = { 1, 2, 0, 1, 2,}; // Plus 1 mod 3
int p2mod3[] = { 2, 0, 1, 2, 0,}; // Plus 2 mod 3
...
case LEFT:  /* Corners: 0 1 5 4     Edges:  0 5 8 4 */
k = gcp[0]; gcp[0] = gcp[1]; gcp[1] = gcp[5]; gcp[5] = gcp[4]; gcp[4] = k;
k = gct[0];
gct[0] = p1mod3[gct[1]];
gct[1] = p2mod3[gct[5]];
gct[5] = p1mod3[gct[4]];
gct[4] = p2mod3[k];
``````

The edge twist is similar to the corner twist, except an edge twist is either 0 or 1. If the blue or green facelet (this applies for edges on the Upper or Down face) is on the Upper or Down face, it is assigned a twist value of 0. If an Upper or Down edge piece is on the middle layer, it is assigned a twist value of 0 if the blue or green facelet is on the Front or Back face. Similarly, if the edge is initially on the middle layer (FL, FR, BR, BL), it is assigned a twist value of 0 if the front or back facelet is on the Upper or Down face, or the Front or Back face.

Turning the Upper, Left, Down or Right face does not change the edge twists. Turning the Front or Back face changes the edge twists.

It was fairly simple to create an algorithm that recursively turns each face and, when at a certain depth (number of moves), checks to see if the four bottom corner and eight bottom edges are in the correct place (and twist). If they are, then this is a move that affects the Upper face.

Throughout my implementation I would test different speed improvements to see if they were effective.

The first test was to try implementing the various corner and edge positions and twists in a bit vector rather than individual elements in an array. The code was approxiately 4-5 times slower on my Intel/AMD based Linux boxes but marginally faster on the PowerPC. I decided to stick with using arrays - the code was both faster and easier to read. It would probably be even faster to implement using fixed variables and not arrays, but it made the code easier to write with arrays. There is a tradeoff between performance and readability. I generally prefer easier to read code. I did not look at implementing any of the code in assembler, even though this was certainly be faster.

#### Move Similarities

Starting at the initial configuration (all faces correct), the first turn moves one of the 6 faces through either 90 degrees, 180 degrees or 270 degrees. There are 18 possible cube states after the first move.

The second move must turn a different face than the previous move. There are 15 possibilites (5 faces through 3 turns). Initially there appear to be 18*15=270 possible combinations. However, if the second move is on an opposite face, there are some similarities. For example, RL is the same as LR, UD is the same as DU. I arbitrarily decided that a turn of the Down, Back or Right face could not occur after a turn of their opposite face (Upper, Front or Back). Thus the code would generate DU, BF, RL as a move sequence, but never UD, FB or LR. There are 27 similaries that are removed, leaving only 243 possible states after two turns.

The third move follows the rules for the second move. There are 3,240 different unique positions after three moves.

The fourth move generates the first non-trivial equivalences. There are 15 pairs of moves that are equivalent:

``````
D2U2B2F2=B2F2D2U2
D2U2R2L2=R2L2D2U2
F2D2U2B2=B2D2U2F2
F2D2U2F2=B2D2U2B2
F2R2L2B2=B2R2L2F2
F2R2L2F2=B2R2L2B2
L2B2F2L2=R2B2F2R2
L2B2F2R2=R2B2F2L2
L2D2U2L2=R2D2U2R2
L2D2U2R2=R2D2U2L2
R2L2B2F2=B2F2R2L2
U2B2F2D2=D2B2F2U2
U2B2F2U2=D2B2F2D2
U2R2L2D2=D2R2L2U2
U2R2L2U2=D2R2L2D2
``````

My first algorithm was very simple - it ignores these similarities. I needed a program that was simple and would generate correct results that further versions of the code could compare against. There are 43,239 unique states after 4 moves.

The fifth move generates even more similarities. There are over 2,000 equivalent moves. There are 575,076 unique states after 5 moves.

The sixth move generates the first set of moves that only affect the Upper face.

``````
RUBU'B'R'
RBUB'U'R'
``````

There are 7,637,395 unique states after 6 moves.

The code took 15 seconds (0:15) to generate all 8 turn moves. The code took 205 seconds (3:25) to generate all 9 turn moves. The code took 2734 seconds (45:34) to generate all 10 turn moves. The number of unique states after each move was increasing by a factor 13-14 for each additional twists. The time taken was increasing by approximately the same. It was clear that an improved algorithm was needed.

The number of unique patterns for the first 7 number of moves is
Number
of moves
New of unique
positions
Multiplier from
previous number
1 18n/a
2 243 13.50
3 3,240 13.33
4 43,239 13.34
5 575,076 13.30
6 7,637,395 13.28
7101,289,960 13.26

The above moves were calculated. Based on a multiplier of 13.25 for the next few moves, the following number of unique positions is indicated.

Number
of moves
Hypothetical number of
unique positions
8 1,342,091,970
9 17,782,718,603
10 235,621,021,483
11 3,121,978,534,651
12 41,366,215,584,131
13 548,102,356,489,737
14 7,262,356,223,489,020
15 96,226,219,961,229,500
16 1,274,997,414,486,290,000
17 16,893,715,741,943,400,000
G0 43,252,003,274,489,800,000
18 223,841,733,580,750,000,000
19 2,965,902,969,944,930,000,000
2039,298,214,351,770,300,000,000

It is known that there are (non-Upper face) moves that require at least 20 face turns. The G0 line is the number of possible unique permunations on the cube.

#### Source Code?

Sorry. I rarely release source code.

#### Second Algorithm

It is unfair to call this the second algorithm because each algorithm was an incremental step from the previous and I had decided on the long car journey the various steps I would use. Once I had a good working algorithm, I would use this to generate the set of moves for the number of moves that could reasonably be calculated. I used these results to test the next version.

#### Rotational and Mirror Symmetries

Consider the first move. If it is a turn of the Upper face, then this is the same as performing a turn of the Upper face at the end of the move. Therefore all moves that start with an Upper face turn can be ignored as the same move will occur with an Upper face turn at the end of the move.

A similar argument applies with all moves that start with the Down face. The same move must exist with the Down face as the last face turned.

There are 4 rotational symmetric moves. Imagine the cube spun around an axis going from the middle of the Upper face through the cube and exiting through the middle of the Down face. The cube can be rotated through 90, 180 or 270 degrees to create rotationally equivalent moves. Any move that starts with the Back, Left or Front face is rotationally equivalent to a move that starts with the Right face. I therefore excluded all moves that start with the Back, Left or Front face and just focused on moves that start with the Right face. If I found a move that only affected the Upper layer, then I would create the rotationally equivalent moves that start with the Back, Left and Front faces.

There is also a mirror symmetry. Any move that affects only the Upper face can be mapped to its mirror with the following mapping:

``````
U  ==> U'
U2 ==> U2
U' ==> U
L  ==> L'
L2 ==> L2
L' ==> L
F  ==> B'
F2 ==> B2
F' ==> B
D  ==> D'
D2 ==> D2
D' ==> D
R  ==> R'
R2 ==> R2
R' ==> R
B  ==> F'
B2 ==> F2
B' ==> F
``````

The mirror moves also only affects the Upper face. Therefore any move that starts with R' has a mirror equivalent that starts with R.

The first move can therefore be constrained to be either R or R2. If a move can be found that only affects the Upper face, then rotational, mirror and mirror rotational moves can be found. For each unique move, there are 7 additional moves. Starting with R or R2 as the first move cuts the problem by 2/18 (or 1/9) giving a 9 fold improvement.

It is thus possible to go a level deeper in a reasonable amount of time.

The code was still too slow for a complete search for the Upper moves.

The next speed-up was to look at the state of the cube one or two moves before the prescribed depth. If, one move before looking for moves at a certain depth, the edge pieces FL and BR are both incorrect, then it is impossible for both to be put in the correct position in one move. Therefore there is no need to look further. This can be extended to checking for FR and BL as well. If neither are in the correct place, no single move can put both in the same place.

Similary, if two moves before a prescribed depth, if none of the edges FR, BL, FD, LD, BD are in their initial location, no two moves can put all the edges in the correct location. Additional checks can be done for similar 5 down and middle layer edges.

These additional checks were sufficient to speed up the algorithm to finding depth 12 moves in a reasonable time (hours not days).

#### Third Algorithm

The computer could generate all of the 7,706,988 six face-turn moves in about a second. This is a reasonable number to store in memory (RAM). If the state of the cube after each of these 7+ million moves could be simply stored, then to find all Upper face moves of a given length (number of face-turns), you would generate all moves up to (length - 6) and then look through all of the 7,706,988 possible patterns to find a move that brings all of the Down face and middle layer back to its initial configuration. This sounds like a longer algorithm, but certain tricks can be used to speed up the search.

I used the following implementation:

There are 8 corners. Each corner position can be represented in 3 bits. Storing all possible corner positions can be done with simple bit shifts in a total 24 bits. (There are only 40,320 unique positions for the corners to be in, but for speed, a simple bit shift was much simpler).

There are 3 possible corner twists (2 bits), 8 corners. The corner twists could be stored in 16 bits.

There are 12 edges. Each edge position is 4 bits. Storing all edge positions is 48 bits.

Each edge twists can be stored in a single bit. All 12 edge twists can be stored in 12 bits.

The state of each move can therefore quickly and easily be stored in 100 bits. I also wanted to store the first move, this used another 5 bits. Padding out to fill out a 32 bit boundary and each move could be stored in 128 bits (16 bytes). There were just under 8M positions, using 16 bytes each is approximately 128Mb. A large number, but something that can easily fit in system RAM.

I needed an efficient method for locating all possible moves that would return to the cube to a configuration where all the facelets, excluding the Upper layer, were correct. The solution was to create a 24 bit hash of the various bits (using XOR). This generated a number in the range (0 .. 2^24) (0 .. 16,777,216). I created an array that contained a linked list of all moves that had a similar hash value.

Thus, given a state, I could determine the transform (which corners to which locations etc.) needed to return the cube to its initial configuration (excluding the Upper layer). Given the transform, I could create the hash. Given the hash, I could look through the linked list at all the moves. This was a huge performance increase. For example, to find all length 13 moves, I only need to look at all length 7 moves. For each length 7 move, I could find the hash needed and would typically only have to look at 1 or 2 moves instead of the 7,700,000 that I used to have to look at.

The hash was relatively simple and worked. I didn't look at improving it. I ran some tests. There are 7,704,126 different positions (some are similar, I decided to ignore the similarities). (There are actually 7,637,398 unique patterns after 6 moves). The size of the linked lists (i.e. the number of moves for a given hash) is shown below:

``````
counter[1]=3939746
counter[2]=800774
counter[3]=397220
counter[4]=146173
counter[5]=39954
counter[6]=16199
counter[7]=6276
counter[8]=2300
counter[9]=1081
counter[10]=564
counter[11]=272
counter[12]=172
counter[13]=78
counter[14]=140
counter[15]=54
counter[16]=55
counter[17]=35
counter[18]=24
counter[19]=8
counter[20]=10
counter[21]=9
counter[22]=8
counter[23]=2
counter[24]=1
counter[25]=0
counter[26]=0
counter[27]=0
counter[28]=0
counter[29]=0
counter[30]=0
counter[31]=0
counter[32]=0
counter[33]=0
counter[34]=4
counter[35]=2
counter[36]=1
counter[37]=0
counter[38]=0
counter[39]=1
``````
The highest number is 39. Thus, for any given position, the most number of moves I need to look at is 39. For over half of the moves, there is only one move to look at. This speeds up the search by several orders of magnitude. Instead of testing over 7 million moves, I only need to look at, on average 1-2 moves.

The code takes approximately 5 seconds to calculate the first six moves and store them in memory. To find Upper moves, I then start with the Right face (R and R2 only), then do the number of twists necessary to make (length - 6). Then I calculate the hash, look to see if there are any moves to return the bottom of the cube to its initial state. If there are any moves, then the various symmetrical moves can be easily calculated. It takes around 5 seconds to generate length 7, 8, 9, 10 or 11. This is similar to the approximate 5 seconds to initialize the 6 move array. It takes 6 seconds to generate length 12 (previouly it was 4 hours). It takes 20 seconds to generate length 13. It takes 192 seconds (3:12) to generate length 14. It took just under 15 hours (14:45) to generate all length 16 moves. It took a few hours to find the remaining moves.

The work above was done on a 512Mb computer. I recently upgraded to a computer with 4Gb RAM. This is sufficient to store moves up to depth 7. It takes the new computer about 40 seconds to create, process and store moves up to depth 7 so it is only useful for calculating moves of depth 14 or higher. Using depth 6 storage, it takes 60 seconds to calculate all upper moves of depth 14. Using depth 7 storage, it takes 50 seconds. For moves of 15 turns, the speed improves from 41:45 (MM:SS) to 4:40.

#### Results

The table below shows the number of Upper face positions that are found for the number of turns and the running total for all Upper face positions up to the number of turns. The first time column is the time taken to run the program on a Linux machine (2.0Ghz/512Mb RAM). The second time column is the time taken to run the program on a Linux machine (3.0Ghz dual core Intel E6850/4Gb RAM)

Number
of moves
New Upper face
positions
Total so far (HH:MM:SS) to run
2.0 Ghz/512Mb
(HH:MM:SS) to run
3.0 Ghz Intel E6850
Dual Core/4 Gb RAM
0 1 10:00:010:00:01
1 3 40:00:010:00:01
2 0 40:00:010:00:01
3 0 40:00:010:00:01
4 0 40:00:010:00:01
5 0 40:00:010:00:01
6 16 200:00:010:00:01
7 88 1080:00:050:00:03
8 200 3080:00:050:00:03
9 394 7020:00:050:00:03
10 1,102 1,8040:00:050:00:03
11 3,470 5,2740:00:050:00:03
12 9,80715,0810:00:060:00:03
1320,50535,5860:00:190:00:08
1420,76856,3540:03:140:00:50
15 5,63061,9840:41:450:04:40
16 22462,2089:08:000:56:08

#### Source Code?

Sorry. I rarely release source code.

#### Mapping of Upper face state to unique number

From the Size of the Problem earlier, there are 62,208 unique upper face combinations. I created a mapping from the state to variables icp, ict, iep, iet that represented the corner positions, twists, edge positions and twists. These values are constrained:

``````
icp = 0..11	(initially 0..23 but then divides by 2)
ict = 0..27
iep = 0..23
iet = 0..8
To calculate icp:

int factorial[] = { 0, 1, 2, 6};
i = 0;
k = 0;
n = 0;
a[0] = gcp[0];
a[1] = gcp[1];
a[2] = gcp[2];
a[3] = gcp[3];

while(i <= 2) {
j = a[i];
k = j * factorial[3-i];
n = n + k;
i++;
for(m=i; m<4; m++) {
if (j < a[m]) a[m] = a[m] - 1;
}
}
ict = n + a[3];
``````

This somewhat awkward looking code will create a number 0-23. The mapping is

``````
icp	gcp[0123]
0	0123
1	0132
2	0213
3	0231
4	0312
5	0321
6	1023
7	1032
8	1203
9	1230
10	1302
11	1320
12	2013
13	2031
14	2103
15	2130
16	2301
17	2310
18	3012
19	3021
20	3102
21	3120
22	3201
23	3210
``````

The variable iep uses similar code (but for edges). Code for ict and iet is simpler:

``````
ict = (gct[0] * 9) + (gct[1] * 3) + gct[2];
iet = (get[0] * 4) + (get[1] * 2) + get[2];
``````

There is one further piece of code. Given a state for the edges, only half of the corner positions are possible. The final piece of code is

``````
icp = int (icp / 2);
``````

Each of the 62,208 different positions can be represented by

``````
n = (iep * (8 * 12 * 27)) + (iet * (12 * 27)) + (icp * 27) + ict;
``````

The format of the results file contains this unique number, but also shows each of the corner and edge positions and twists. This file has a rather ugly format, but I tried to output in a form that others can easily parse. Each line is a unique entry of the form

``````
un=xxxxx epn=xx etn=x cpn=xx ctn=xx ep=AAAA et=BBBB cp=CCCC ct=DDDD D=xx m=move fm=move in Singmaster notation

un = unique number in the range 0..62,207
epn = edge position number (same as iep above)
etn = edge twist number (same as iet above)
cpn = corner position number (need to multiply by 2 and then look up in chart above)
ctn = corner twist number (same as ict above)
ep = edge positions for edge 0, 1, 2, 3
et = edge twist for edge position 0, 1, 2, 3
cp = corner positions for corner 0, 1, 2, 3
ct = corner twist for corner position 0, 1, 2, 3

for all cases,
un = (epn * (8 * 12 * 27)) + (etn * (12 * 27)) + (cpn * 27) + ctn;

D = length of move
m = move where
A = U
B = U2
C = U'
D = L
E = L2
F = L'
G = F
H = F2
I = F'
J = D
K = D2
L = D'
M = R
N = R2
O = R'
P = B
Q = B2
R = B'
fm = move in Singmaster notation
``````
I used this somewhat obscure format to allow an easy download, import and conversion. The values epn, etn, cpn, ctn can be calculcated from ep, et, cp and ct respectively.

#### How to Look Up a Move

The numbering scheme can be a little confusing.

Example with just moving corners, no twists

I find it easiest to calculate the values for iep, iet, icp, ict and then look up the corresponding number. The results file uses similar nomenclature (epn, etn, cpn, ctn for edge/corner position/twists number).

Let's say you want to find a move that does not moves or twist the Upper edges, but moves three of the corners in a clockwise manner, keeping URF in position. In other words, the piece at UFL goes to ULB, the piece at ULB goes to UBR, the piece at UBR goes to UFL. The iep, iet and ict are all 0.

The corners are numbered 0, 1, 2, 3 starting with UFL and going anti-clockwise (ULB, UBR, URF). Using this numbering scheme, the effect of the move will be for corner 2 piece to be in the corner 0 location, the corner 0 piece will be in the corner 1 location and the corner 1 piece will be in the corner 2 location. Corner 3 is unchanged. Therefore we are looking for a move where the corner positions can be respresented as 2013. We look up 2013 in the table above and see that this is represented by 12. However the icp must always be divided by 2. So, we are looking for a move with an (epn=00, etn=0, cpn=6, ctn=0). We can convert this is the unique number using the formula:

``````
un = (epn * (8 * 12 * 27)) + (etn * (12 * 27)) + (cpn * 27) + ctn;
``````

In this case, un=162 (6*27). The move is L2B2L'F'LB2L'FL'

Example with just moving edges, no twists

Find the move with swaps each edge with the piece opposite it, nothing else moves. In other words UF and UB switch places, so do UL and UR. Edges are numbers with UL=0, UB=1, UR=2 and UF=3. We need a move where after the move the edges are 2301. Looking this up in the table above, iep=16. The edges are not twisted (iet=0). The corners are unchanged (icp=0, ict=0). From the formula, un=41472. The move is LRU2L'R'F'B'U2FB

Example with moving and twisting edges

Find the move that moves the edges (UF, UB, UR) in an anti-clockwise circle. The edges UB and UR both need flipping. Edges are numbers with UL=0, UB=1, UR=2 and UF=3. We need a move where after the move the edges are 0231. Looking this up in the table above, iep=3. The edge currently at UL remains untwisted. The edge currently at UB is moved to UF and then twisted. The edge currently at UR is moved to UB and then twisted. The edge currently at UF is moved to UR. To calculate the twists, look at the piece AFTER it has been moved. In this case, the piece that ends up at UB and UF are twisted. To calculate edge twists, we add up the values if the edge needs twisting (UL=1, UB=2, UR=4). In this case, UB needs twisting, so we need iet=2. Note that the twisted is looked at AFTER the piece has moved. This can be confusing. As in the previous case, icp=0, ict=0. From the formula, un=8424. The move is L'RD'BDLR'B'U'B.

Example with just twisting corners

Find the move that twists URF clockwise and UBR anti-clockwise. The values iep, iet, icp are all 0. For twists, we just look at corner positions 0, 1, 2 (UFL, ULB, UBR). Assuming a green upper face, we want the green facelet of the UBR corner to go to the Right face. This is twist 2. We want the twists to be 002 (as seen from positions 012). This is 2 * (3*3) = 18. So, we are looking for a move with an (epn=00, etn=0, cpn=0, ctn=18). Doing the calculations, un=18. The move is LFL'F2RU2R'U2FL'U2LU2

Complex Example

Find that move that will solve a cube after FURU'R'F' is applied to a cube in its initial state.

First, look at the edge positions. Position 0 (UL) is correct, no twists needed. Position 1 (UB) needs the piece at position 2 (UR). The piece moving into place does not need twisting. Position 2 (UR) needs the piece at position 3 (UF). This piece does need twisting. Position 3 (UF) needs the piece at position 1 (UB). The edge positions move is 0231. Looking this up, the edge position move is 3. The edge twists are 0011; to look this up we only need the first three edges, which is 001. The edge twist is 1 * (2^2) = 4.

Second, look at the corners. Corner 0 (UFL) needs the piece at corner 3 (URF) with no twists. Corner 1 (ULB) needs the piece at corner 2 (UBR) with no twists. Corner 2 (UBR) needs the piece at corner 1 (ULB). This corner needs an anti-clockwise twists, which is a value of 2. Corner 3 (URF) needs the piece at corner 0 (UFL). The corner position is 3210, looking this is up is a value of 23. We need to divide by 2 for a lookup value of 11. The corner twists are 002, which is a value of 2 * (3 * 3) = 18.

So, we are looking for a move with an (epn=03, etn=4, cpn=11, ctn=18). un = (epn * (8 * 12 * 27)) + (etn * (12 * 27)) + (cpn * 27) + ctn; This has a value of (3 * (8 * 12 * 27)) + (4 * (12 * 27)) + (11 * 27) + 18=9387. The move is FRUR'U'F' The full results are in Upper face results file . To help with parsing, the initial state is shown as being reached in two moves.

#### Errors

Assuming I programmed correctly, none. But, there is some significant code to speed up the search, so errors in the coding are possible.

Last updated: November 12, 2007.