| 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.
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. More InformationSolving the Rubik's Cube Optimally is NP-complete Related ArticlesRubik's cube - the order of God's Number 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
or email your comment to: comments@i-programmer.info |
|||
| Last Updated ( Monday, 03 July 2017 ) |
