Optimality and God’s number

What makes the combinatorial optimization problem tricky is that we’re not looking for any solution; we’re in fact interested in the optimal solution of the problem. So, what is the difference? Right after the Rubik’s cube was invented, it was known how to reach the goal state (but it took Ernő Rubik about a month to figure out the first method of solving his own invention, which I expect was a frustrating experience). Nowadays, there are lots of different ways or schemes of cube solving: the beginner’s method (layer by layer), the method by Jessica Fridrich (very popular among speedcubers), and so on.

All of them vary by the number of moves to be taken. For example, a very simple beginner’s method requires about 100 rotations to solve the cube using just 5…7 sequences of rotations to be memorized. In contrast, the current world record in the speedcubing competition is solving the cube in 3...