5 ms·

Solving the Rubik's Cube Optimally Is NP-Complete

72 points by seycombi 9y ago

js8 9y ago
Interesting. I wonder, if you can solve 5x5x5 cube, then you can solve them all. How good an approximation is using the optimal methods for solving 5x5x5 to solve the NxNxN case?
- dtech 9y ago
  If the NxNxN case is NP-complete, then that currently known optimal method will still require an N^k amount of steps.
- Extigy 9y ago
  I'm not sure that's true. I much prefer solving my 5x5x5 rather than my 4x4x4 because I always forget the algorithms for the extra parity that even cubes provide. I don't think I could solve a 6x6x6 with the 5x5x5 algorithms I know.
  - Zanni 9y ago
    It's been a while so maybe I'm misremembering, but can't you solve a 4x4x4 by reducing it to a 3x3x3 and solving that? Pretty sure that's how I used to do it. Treat each 4 as a 3 with a fat middle: 1-2-1. Then solve the centers (2x2) and the edges (2x1) with standard moves and you've got, essentially, a 3x3x3.
    - timjver 9y ago
      A 4x4x4 definitely has parity issues that don't arise on a 3x3x3.
    - captn3m0 9y ago
      4x4x4 has parity problems, same as 5x5x5, but as the GP posted, the number of parity cases for 4x4x4 is higher, which makes it slightly more difficult. (I prefer solving the 5x5x5 for exactly the same reason).
  - deleted 9y ago
    [deleted]
- tripa 9y ago
  What optimal methods are you referring to? The paper doesn't really define one, and real world cubers sure don't use any. Assuming you mean real life cubes, the most common [1] method to solve anything bigger than 3×3×3 is to first reduce to 3×3×3, then solve as a normal 3×3×3 using outer slice turns. On even-sided cubes, that reduction process is sensitive to a number of so-called "reduction parities", meaning in a nutshell that you might be recreating edges [2] in a configuration that isn't possible/solvable on a 3×3×3. This can't happen with odd cubes, because the center piece on faces and edges disambiguates from the start. So really, most of what you need to know about solving big cubes is there on a 4×4×4, and not on a 5×5×5. To make it fully pedantry-proof [3], you need to know standard methods for both 4×4×4 and 5×5×5, both of which already require solving a 3×3×3. [1] There are alternate methods that are actually used for 4 or 5 and don't have the "parity weakness", but they don't scale well enough to anything bigger. [2] Or, obviously, faces, but in real life reducing faces in a valid configuration is considered a prerequisite. [3] It kind of depends on who you ask whether or not the reduction methods are "the same" moving from 4×4×4 to 5×5×5. They're a direct extension, but they do involve pieces with no counterpart.
pge 9y ago
When my daughter got into rubik's cube with her friends, I thought it would be fun to use it as a sample to teach her about applying a simple breadth-first solver to find the shortest path to a solution. Embarrasingly, I neglected to do the math on how many possible states there were before we started. We coded up the solver in just a few minutes, but quickly discovered that a typical solution would take longer than either of our lifetimes...Oops. She learned some coding that day - not the lesson I intended, but probably a more important one!
- timjver 9y ago
  It only took you a few minutes, together with your daughter, to write code that lets you interact with a Rubik's Cube? Or were you only referring to the solver part?
  - tripa 9y ago
    Even the solver part is impressive. A BFS is a few seconds, but modeling a Rubik's cube properly in a way a daughter would understand is... harder.
    - pge 9y ago
      Yes, that part was over her head. I did all the coding, and the representation of the cube and the moves. She got the concepts of the search, but capturing the changes in the cube when a face is rotated was too complicated to do with her.
  - pge 9y ago
    It was just a simple solver - you typed in the faces at a command line, and it spit out the moves. It was brute force breadth-first, so nothing fancy...
amelius 9y ago
How hard would it be on a quantum computer?
- kirrent 9y ago
  That's a pretty fundamental question, but probably QMA?
- maxander 9y ago
  To my knowledge, the current opinion (with no known proof) is that quantum computers can't efficiently solve NP-hard problems. So, the answer is (probably) "still hard," but I haven't the slightest how that would be formally described.
williamstein 9y ago
One of the coauthors of the paper is also a serious web developer: https://github.com/edemaine/coauthor https://github.com/edemaine/coauthor
crb002 9y ago
It's constant time unless you grow the cube.

72 points by seycombi 9y ago

js8 9y ago

Interesting. I wonder, if you can solve 5x5x5 cube, then you can solve them all. How good an approximation is using the optimal methods for solving 5x5x5 to solve the NxNxN case?

dtech 9y ago
If the NxNxN case is NP-complete, then that currently known optimal method will still require an N^k amount of steps.
Extigy 9y ago
I'm not sure that's true. I much prefer solving my 5x5x5 rather than my 4x4x4 because I always forget the algorithms for the extra parity that even cubes provide. I don't think I could solve a 6x6x6 with the 5x5x5 algorithms I know.
- Zanni 9y ago
  It's been a while so maybe I'm misremembering, but can't you solve a 4x4x4 by reducing it to a 3x3x3 and solving that? Pretty sure that's how I used to do it. Treat each 4 as a 3 with a fat middle: 1-2-1. Then solve the centers (2x2) and the edges (2x1) with standard moves and you've got, essentially, a 3x3x3.
  - timjver 9y ago
    A 4x4x4 definitely has parity issues that don't arise on a 3x3x3.
  - captn3m0 9y ago
    4x4x4 has parity problems, same as 5x5x5, but as the GP posted, the number of parity cases for 4x4x4 is higher, which makes it slightly more difficult. (I prefer solving the 5x5x5 for exactly the same reason).
- deleted 9y ago
  [deleted]
tripa 9y ago
What optimal methods are you referring to? The paper doesn't really define one, and real world cubers sure don't use any. Assuming you mean real life cubes, the most common [1] method to solve anything bigger than 3×3×3 is to first reduce to 3×3×3, then solve as a normal 3×3×3 using outer slice turns. On even-sided cubes, that reduction process is sensitive to a number of so-called "reduction parities", meaning in a nutshell that you might be recreating edges [2] in a configuration that isn't possible/solvable on a 3×3×3. This can't happen with odd cubes, because the center piece on faces and edges disambiguates from the start. So really, most of what you need to know about solving big cubes is there on a 4×4×4, and not on a 5×5×5. To make it fully pedantry-proof [3], you need to know standard methods for both 4×4×4 and 5×5×5, both of which already require solving a 3×3×3. [1] There are alternate methods that are actually used for 4 or 5 and don't have the "parity weakness", but they don't scale well enough to anything bigger. [2] Or, obviously, faces, but in real life reducing faces in a valid configuration is considered a prerequisite. [3] It kind of depends on who you ask whether or not the reduction methods are "the same" moving from 4×4×4 to 5×5×5. They're a direct extension, but they do involve pieces with no counterpart.

pge 9y ago

When my daughter got into rubik's cube with her friends, I thought it would be fun to use it as a sample to teach her about applying a simple breadth-first solver to find the shortest path to a solution. Embarrasingly, I neglected to do the math on how many possible states there were before we started. We coded up the solver in just a few minutes, but quickly discovered that a typical solution would take longer than either of our lifetimes...Oops. She learned some coding that day - not the lesson I intended, but probably a more important one!

timjver 9y ago
It only took you a few minutes, together with your daughter, to write code that lets you interact with a Rubik's Cube? Or were you only referring to the solver part?
- tripa 9y ago
  Even the solver part is impressive. A BFS is a few seconds, but modeling a Rubik's cube properly in a way a daughter would understand is... harder.
  - pge 9y ago
    Yes, that part was over her head. I did all the coding, and the representation of the cube and the moves. She got the concepts of the search, but capturing the changes in the cube when a face is rotated was too complicated to do with her.
- pge 9y ago
  It was just a simple solver - you typed in the faces at a command line, and it spit out the moves. It was brute force breadth-first, so nothing fancy...

amelius 9y ago

How hard would it be on a quantum computer?

kirrent 9y ago
That's a pretty fundamental question, but probably QMA?
maxander 9y ago
To my knowledge, the current opinion (with no known proof) is that quantum computers can't efficiently solve NP-hard problems. So, the answer is (probably) "still hard," but I haven't the slightest how that would be formally described.

williamstein 9y ago

One of the coauthors of the paper is also a serious web developer: https://github.com/edemaine/coauthor https://github.com/edemaine/coauthor

crb002 9y ago

It's constant time unless you grow the cube.