Rubik's Cube algorithm with Optimal Algorithm

Question

I'm confused about Thistlewaite's, Kociemba's, and Korf's algorithms for optimal Rubik's cube solving. What are the differences and how is each of the groups defined for each algorithm? I understood that with each group, they're trying to get rid of faces that require corner turns. What I don't understand is what state should the cube be in to be defined as a subset of the group (e.g. edges or corners turned in a specific orientation).

Answer 1

I think you are aware of the general idea but for the uninitiated, let me try to explain the techniques involved for solving the Rubik's Cube optimally.

Let's start with a strategy called the Layer-By-Layer method. We start with a completely scrambled cube, and as we solve it, we hit certain checkpoints. These checkpoints are:

Checkpoint 1: any scramble.
Checkpoint 2: the first layer is solved.
Checkpoint 3: the first two layers are solved.
Checkpoint 4: the first two layers are solved and the last layer is oriented correctly.
Checkpoint 5: a completely solved cube.

So using this Layer-By-Layer method, how many moves do we need to solve a cube? Well, consider going from Checkpoint 1 to Checkpoint 2. I'm going to make up numbers for demonstrative purposes (I have no idea what the actual numbers are). Through careful counting (computers may help here), let's say it always takes 20 moves or less to go from Checkpoint 1 to Checkpoint 2.

Then do the same for Checkpoint 2 to Checkpoint 3. Say we determine that it always takes 13 moves or less. Now do the same for 3 to 4, and 4 to 5.

And when you add it all up (20 + 13 + ...) let's say we get 50 moves. Great! We have just proven that we can solve any cube in 50 moves or less!

But wait, you say, there must be a better way! And you'd be right. Let's say instead that we used a different method instead of Layer-By-Layer. Let's say instead we used something I'm gonna make up and call the Two-Step method. It has checkpoints that look like this:

Checkpoint 1: any scramble.
Checkpoint 2: the first two layers are solved.
Checkpoint 3: a completely solved cube.

Notice that these are the same checkpoints as before, we just skipped some. Now when we count how many moves it takes to go from Checkpoint 1 to Checkpoint 2, using careful counting (and more powerful computers), suppose we get 22 moves. (Again, I'm just totally making up numbers here). And going from Checkpoint 2 to Checkpoint 3 suppose we get 18 moves. Now we've just proven that we can solve any cube in 40 moves or less, which is better than our previous result.

This is the essence of Thistlethwaite's algorithm and Kociemba's algorithm. Kociemba's algorithm is the same as Thistlethwaite's algorithm but with less checkpoints.

The other main difference between my made up example and Thistlethwaite's/Kociemba's algorithm is that the checkpoints chosen are way more optimal and lead to much more efficient solves of the cube. For example, here are the checkpoints for Thistlethwaite's algorithm:

Checkpoint 1: any scramble.
Checkpoint 2: any scramble starting from a solved cube except you can't use quarter turn moves for U and D (must use U2 and D2).
Checkpoint 3: any scramble starting from a solved cube except you can't use quarter turn moves for U, D, F, and B (must use U2, D2, F2, and B2).
Checkpoint 4: any scramble starting from a solved cube except you can't use quarter turn moves at all.  can only use half turns.
Checkpoint 5: a completely solved cube.

So these checkpoints are much more difficult for humans to verify, but they are no problem for computers. For example, it's easy to see if the first layer is solved, but it's not so obvious that we have a scramble obtained without using quarter turns for U and D.

So to more directly answer your question, the checkpoints involved with Thistlethwaite's algorithm and Kociemba's algorithm are less about "these cubies must be in these positions" and more like "the cube state must have this property". For example take Thistlethwaite's Checkpoint 4. You can scramble a cube using only half turns. Well, this is a relatively easy thing to check for: colors can only be their original side or the opposite side, eg a blue square can only appear on the side of the cube with a blue or green center. So that's the property the cube state must have. But notice that doesn't lock any particular square to be in any particular place.

Korf's algorithm (and beyond) are further improvements to Thistlethwaite's algorithm and Kociemba's algorithm. The main idea remains the same, it's just that the method for counting gets increasingly clever. This wikipedia article I think does a fairly good job of explaining it.

Hope that helps!