What is the maximal number of steps that a computer (using the fastest algorithm) would need to solve an arbitrary 2x2x2 Rubik's Cube configuration?
Are there any other known algorithms that will perform similarly fast?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ I believe it's 11, and you can do it through exhaustive search (there are only about 2 million configurations). $\endgroup$– user88Jun 11, 2014 at 21:57
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
From http://en.wikipedia.org/wiki/Pocket_Cube:
The maximum number of turns required to solve the cube is up to 11 full turns, or up to 14 quarter turns.
As for an efficient algorithm, there are only ~3.7M configurations1 that the 2x2x2 cube can have, so it would not be unreasonable to store the solution for each of these positions in a look-up table. You can generate the look-up table by starting with a solved cube and "scrambling" it to arrive at each of the 3.7M configurations (keeping track of your turns along the way) and then "backtrack" to solve the cube from that configuration.
There are also efficient algorithms for the 3x3x3 cube, such as Korf's Algorithm, which you may be able to employ when solving the 2x2x2 cube. However, note the following:
Although this algorithm will always find optimal solutions there is no worst case analysis. It is not known how many moves this algorithm might need.
1 As opposed to the 3x3x3 cube for which there are 43,252,003,274,489,856,000 configurations.
-
$\begingroup$ Why can't exist an efficient algorithm with out look up table? $\endgroup$– klm123Jun 12, 2014 at 5:17
-
$\begingroup$ You need to store a lot of data and you have to look up one thing in a collection of 3.7M items. Maybe with a tree it is fast enough. So if you have a server let it calculate all possible answers store it in a tree and you can search for an answer in a small amount of time. $\endgroup$ Jun 12, 2014 at 7:42
-
$\begingroup$ Why do you need to store a lot of data when you do not use lookup table? There are efficient algorithms for 3x-cube solution for humans, they speeds are lower than the speed of computer algorithms (20). Why for 2x-cube the speed of both can't be the same (11)? $\endgroup$– klm123Jun 12, 2014 at 13:07
-
$\begingroup$ @klm123 Do you want your algorithm to necessarily return the solution in the fewest number of moves? $\endgroup$– arshajiiJun 12, 2014 at 13:08
-
1$\begingroup$ @klm123 But there is no guarantee that the human algorithms will produce such a solution. $\endgroup$– arshajiiJun 12, 2014 at 13:13