Rubik's Cube Is Hard - NP Hard
Rubik's Cube Is Hard - NP Hard
Written by Mike James   
Monday, 03 July 2017

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. 

rubik17twist

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 n2/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 fo anything other than a 3x3x3 cube. 

 rubikdoodle

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, FacebookGoogle+ or Linkedin.

 

 

Banner


Revealing the Who and Why of Node.js Use
27/07/2017

Having released the findings of its second annual survey, the Node.js Foundation says that Node.js is emerging as a universal development framework with a broad diversity of applications. We look [ ... ]



Python Heads IEEE Spectrum Language Ranking
19/07/2017

The language that comes top in this year's IEEE Spectrum Ranking is Python, closely followed by C and Java. However if you think another language should be the most popular one, simply use its interac [ ... ]


More News

 

 
 

 

blog comments powered by Disqus

Last Updated ( Monday, 03 July 2017 )
 
 

   
Banner
RSS feed of news items only
I Programmer News
Copyright © 2017 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.