Optimal solutions.

Optimal solutions.


The Layer by Layer and the Fridrich solution are certainly not optimal, but just very usable for humans. One of the goals of this webpage is to tell you more about optimal solutions, which has been a question for more than 30 years. The question is: "What is the maximum amount of required moves to solve any instance of the Rubik's Cube?".

Measure.

There are two common ways to measure the length of a solution. The first is to count the number of quarter turns. The second is to count the number of face turns. A move like F2 (a half turn of the front face) would count as 2 moves in the quarter turn metric and as only 1 move in the face metric. Most research is done for the face turn metric because turning a face half way can be done in one action of your hand. It is also mathematically easier to work with.

Brute force.

In computer science, brute-force search, is a trivial but very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement. For example, a brute-force algorithm to find the divisors of a natural number n is to enumerate all integers from 1 to n, and check whether each of them divides n without remainder. The problem is that when figures get large, executing time will expand linearly to thousands of years which isn't what we want to wait for. So, in our case, where the number of possible positions is so extremely large, we have to come up with something smarter. Ofcourse, we can use a few simple tricks (symmetry arguments) to lower the amount of positions to check by a factor 48, but that still won't be doable in a reasonable amount of time. First, i will tell more about the exhaustive search, and then a already much better approach.

Brute forcing the cube.

A method of calculating the diameter of the Rubik's Cube can be done like this.

*List all possible positions.

*For every position, calculate the distance to the origin.

*Find the greatest distance, this is God's Number.

Well, as you might suspect, this will take a tremendous amount of time. A much better approach is this.

Note the origin. This has distance 0 to the origin.

Then, write down all positions that have distance 1 to the origin.

Then, write down all positions that have distance 2 to the origin.

Proceed in this manner until you have found all positions. The latest found position(s) have the greatest distance to the origin.

This method is already a lot faster, but it has some difficulty in finding positions of distance, lets say, 15. Here is a method how to do this:

Set A={id}, B={} and C=[id].

For all positions in A apply all elementary moves (F, U2, D', ...) and put them in B.

For all positions in B, check if you allready found these positions stored in C. If so, then you can delete these entries.

Set C==C join [B], A==B.

Repeat until no more positions are found that you already haven't found. The number of rows in C is God's Number.

This algorithm is already a lot faster, and works pretty fast for small sets, like the 2x2x2 cube, or a restricted 3x3x3 cube. But its still too slow to calculate the diameter of the real Rubik's Cube.