Take the 2-minute tour ×
Puzzling Stack Exchange is a question and answer site for those who study the creation and solving of puzzles. It's 100% free, no registration required.

What is the maximal number of steps computer would need to solve an arbitrary 2x2x2 rubiks cube configuration (if he does it as fast as it can)?

Are there known algorithm, which will perform similarly fast?

share|improve this question
    
I believe it's 11, and you can do it through exhaustive search (there are only about 2 million configurations). –  Joe Z. Jun 11 at 21:57

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
    
Why can't exist an efficient algorithm with out look up table? –  klm123 Jun 12 at 5:17
    
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. –  martijnn2008 Jun 12 at 7:42
    
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)? –  klm123 Jun 12 at 13:07
    
@klm123 Do you want your algorithm to necessarily return the solution in the fewest number of moves? –  arshajii Jun 12 at 13:08
    
in <= 11 moves. –  klm123 Jun 12 at 13:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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