If you find solving Rubik's cube difficult you will be pleased to learn that it really is. It has now been proved that working out if a random cube is solvable in exactly n moves is NP complete. 

Rubik's cube is a combinatorial puzzle that has generated a lot of interesting math. For example, we know that any 3x3x3 cube can be solved in a maximum of 20 moves and this is known as "god's number" because it is assumed that to know it you have to be a god. I suppose that 20 moves isn't that many for any starting point for a 3x3x3 cube and this suggests that the task isn't that hard after all. This seems all the more remarkable when you are told that there are 43,252,003,274,489,856,000 potential positions  The majority of solutions take between 15 and 19 moves to solve. There are only around 300,000,000 positions that require 20 moves to reach a solution. See: Rubik's cube Breakthrough

However, it is worth pointing out that we don't know god's number for any larger cube. It took several years of computing time to find the value for the 3x3x3 cube by what amounts to brute force calculation. Finding the value for larger cubes in the same way would take far too long. 

What we do know is that god's number increases like n²/log n. This is a result that was obtained by Erik Demaine, Sarah Eisenstat, and Mikhail Rudoy - the team that has produced the latest result.

We first have to convert the Rubik cube into a decision problem. Can a particular cube be solved in exactly n moves? This is an NP problem because, if you give me an n-move sequence that solves the cube, I can check and hence prove that it can be solved in n moves in polynomial time. However, if I don't have a solution handed to me for checking then it turns out that it is a difficult problem. In fact it is an NP complete problem, which means if you can find a polynomial solution for it then you have found a solution for all problems in NP and you have proved that NP=P, which would earn you the million dollar prize from the Clay Mathematics Institute - not to mention fame and fortune and the key to all of the encryption systems we currently use. 

The key to proving this is to show that the problem is the same as finding a route that visits the nodes of a particular graph just once, a Hamiltonian Cycle - and this problem is known to be NP complete.

So answering the question of whether a particular cube can be solved in n moves is NP complete and hence NP hard. Unless P=NP, it looks increasingly likely that we will never know God's number for anything other than a 3x3x3 cube. 

More Information

Solving the Rubik's Cube Optimally is NP-complete

Related Articles

Rubik's cube breakthrough

Rubik's cube - the order of God's Number

Lego Solves Rubik Really Fast

Google Doodle Rubik's Cube

17x17x17 Rubik Cube Solved In 7.5 Hours

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info