If you take a solved cube and create a graph of all possible moves, you can solve the cube by finding the current cube and following the shortest path back to the solution.  This approach is known as “God’s algorithm” as God would be able to easily visualize the graph and know the perfect solution.  Until the summer of 2010 no one had been able to create the graph as it simply required too much processing time.  Researches, using 35 years worth of CPU time (current desktop PC) from Google, accomplished the task in July of 2010 proving that Rubik’s Cube can always be solved in 20 moves or less (see http://www.cube20.org/).

I have to admit it is a little disappointing to have the problem solved as I have also tried to tackle the problem.  In 2004 I was able to create graphs of approximately 7 moves from the origin (solved state) using a standard PC.  In 2009 I looked at using nVidia’s CUDA architecture to tackle the problem.  That said, now that we know the answer, we can still look for ways to improve the algorithm.  Could a standard PC be used to solve the problem?  What about the 4x4x4 cube (Rubik’s Revenge)? or the 5x5x5 cube (Professor’s Cube)?