2
$\begingroup$

I'm currently studying the 3x3x3 rubik-cube-solving algorithms developed by Kociemba, Korf, and Thistlethwaite and I'm interested in understanding their computational complexities.

Could someone please explain or provide the Big O notation for the time complexity of these algorithms?

$\endgroup$

2 Answers 2

2
$\begingroup$

As noted in the answer of codeR Big O notation makes no sense for 3x3x3 alone because of the constant input size. What might be interesting to discuss is the time complexity to find a solution with these algorithms in relationship to the length of the optimal (=shortest) solution to solve a Rubik's cube. So we divide the cube space in classes which need 0 .. 20 moves to be solved.

The empirical distribution for 1.000.000 random cubes is shown in this diagram. For the exact sizes up to 15 moves see for example here. No cube needs more than 20 moves since God's number is 20.

Thistlethwaite's algorithm:

Without going into details it works with 4 steps and precomputed tables wich give the solution moves for each step just by table lookup. So the solution time is more or less constant and does not depend on the length of the optimal solution. The maximum solution length is 52.

Korf's algorithm:

It uses IDA* to optimally solve a Rubik's cube. It looks for solutions with increasing length until it succeeds and the algorithm returns the optimal solution, which is <= 20. The heuristic function is implemented as pattern databases in memory. Korf himself describes the performance as $t\approx n/m$ where t is the running time, m is the amount of memory used and n is the size of the problem space. The size of the problem space for Rubik's cube (more exactly the number of positions which need to be checked) increases exponentially with a branching factor of about 13.3, so that it will take approximately 13 times as long to find the optimal solution with this method for a cube which has optimal length 18 compared to a cube which has optimal length 17. The maximum solution length is obviously 20.

Kociemba's algorithm:

It uses IDA* to find optimal and suboptimal solutions in phase 1 to transfer the cube into a certain subgroup and then again uses IDA* to completely solve the cube in this subgroup. A modern Python version of my algorithm holds pattern databases in memory with complete information so that it only takes linear time to find the optimal solution in phase 1 and phase 2 in relation to the length of the optimal solutions in phase 1 and phase 2. Since the optimal solution for phase 1 has a maximum length of 12 and for phase 2 of 18, the first solution has at most 30 moves.

But a central part of the algorithm is to generate suboptimal solutions in phase 1 which then are combined with the optimal solution of phase 2 to achieve shorter overall solutions. The number of suboptimal solutions in phase 1 also increases exponentially with the length of the suboptimal solutions (presumably also with a factor about 13). In principle you can run the algorithm until it finds a phase 1 suboptimal solution for which the phase 2 solution has length 0. In this case you have found the optimal solution.

But this is not the intention of the algorithm. Usually you just run it until the desired total length (phase 1 length + phase 2 length) is below a certain treshhold. So for random positions you will find solutions with <=20 moves typically within fractions of a second. The difference to Korf's algorithm is that they are not proved to be optimal. For or a more detailed discussion of the runtime behaviour see the README of the Python implementation mentioned before.

$\endgroup$
4
  • $\begingroup$ Thank you very much for your answer. I had a question about your algorithm; is there a paper that explains it? I need to cite a paper for my work where I have to explain your two-phase algorithm, but I haven't found one that explains it. $\endgroup$
    – Lisa
    Commented Apr 3 at 13:00
  • 1
    $\begingroup$ On my homepage kociemba.org/cube.htm you find quite a lot of information. $\endgroup$ Commented Apr 3 at 18:43
  • $\begingroup$ Thank you, I forgot to delete my comment. I found your website and spent the last 6 hours analyzing your algorithm. I also tested your cube explorer. I have just one remaining question about the cube explorer. Does it offer a function that allows me to see how many seconds it took to find the solution? It works very fast, but I wanted to measure the time, and I was wondering if there might be a function that shows the time. $\endgroup$
    – Lisa
    Commented Apr 3 at 20:00
  • 1
    $\begingroup$ If you are able to run Python code you should take a look at github.com/hkociemba/RubiksCube-TwophaseSolver Here you can generate some statistics. $\endgroup$ Commented Apr 3 at 22:30
2
$\begingroup$

Recall that the time complexity of an algorithm is expressed in terms of its input size. The growth rate of this complexity measure is usually expressed in terms of an asymptotic notation such as Big-oh. For a fixed-sized cube, any reasonable algorithm would take a constant amount of time to solve; however, the constant can be very large. All three of the mentioned algorithms are specific to solving the standard 3 x 3 x 3 Rubik's cube; thus, they may not work for any general cube of larger size.

Out of the three, Korf's algorithm gives the best upper bound, which is 18 face turns. If you are interested in the raw performance of the three heurictic approaches, it does not seem there is a clear winner and requires further research and/or experimental investigation.

Read more here and here.

$\endgroup$
2
  • $\begingroup$ Please see this and this $\endgroup$
    – codeR
    Commented Mar 20 at 12:42
  • $\begingroup$ Yes, you are right. That's why I said a comprehensive investigation is yet to be done. Maybe other community member can better address your issue. $\endgroup$
    – codeR
    Commented Mar 20 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.