Algorithm Solves Rubik's Cubes of Any Size

An anonymous reader writes with this excerpt from New Scientist: "Only the most hardcore puzzle-solvers ever go beyond the standard 3x3x3 Rubik's cube, attempting much larger ones. Now an algorithm has been developed that can solve a Rubik's cube of any size. It might offer clues to humans trying to deal with these tricky beasts. Erik Demaine, a computer scientist at the Massachusetts Institute of Technology has found that the maximum number of moves that will ever be required for a cube of side n is proportional to n/log n. 'It gives me a couple of ideas how to solve this thing faster,' says Stewart Clark, a Rubik's cube enthusiast who owns an 11x11x11 cube."

Comments

From TFA...

[Lightborn]

It's n^2/log n.

Re:From TFA...

[RussellSHarris]

Actually, it's n²/log n, but since Slashdot doesn't like Unicode it just eats that ² character and you end up with n/log n. Which, of course, is wrong.

Re:From TFA...

[arth1]

Yeah, I kind of wondered about that. It would imply that a standard 3x3 cube would always be solvable in 7 moves or less, which is clearly wrong, unless these are gentoo moves.

Re:From TFA...

[Kamiza Ikioi]

Time Cube cannot be solved in 7 moves with stupid educators.

Yes, but...

[Anonymous Coward]

Does it scale to >3 dimensions?

Well that's not good

[Psychotria]

I've been working on my 60x60x60 cube for 17 years now and have 5 cublets in place on one side. This news has ruined my day :-( At my current rate I am never going to finish according to TFA, especially since I am essentially just doing random moves. Damn.

Re:Well that's not good

[FrootLoops]

If you started the Towers of Hanoi puzzle in the usual state, the minimum solution uses 2^100 - 1 moves. One move per second would take about 4*10^22 years, or about 3*10^12 times the age of the universe.

Re:Well that's not good

[BeardedChimp]

The man was devastated by the article and as soon as he overcomes his devastation you tell him his other 12 year life long pursuit is fruitless. He is not going to be having a good day.

Re:Pull off the stickers!

[Korin43]

According to this, at least 2700 people can solve a rubik's cube in 30 seconds. The fact that one of them is on Slashdot wouldn't be particularly surprising.

Re:Solving != best solution

[barrtender]

The headline claims they can "solve" any Rubik's cube, but who cares? You can solve it just by performing random moves.

The import part is NOT solving it, it's that they can do it in the minimum number of moves.

Can you prove that?

Hint: Random moves has a number of infinite move cases that never get solved.

Re:Pull off the stickers!

[Galaga88]

What would be particularly surprising, would be if only one of them was on Slashdot.

General algorithm already known

[Michael Woodhams]

Once you can solve a size 4 and size 5 cube, all larger sizes are obvious generalizations of the same algorithm. (At least, for the algorithm I use it is so.) I've seen an edited video of someone solving a (computer simulated) size 100 cube. So the fact of a "general algorithm" is not news.

That it is an efficient algorithm and sets a new* upper bound on how many moves you need is interesting. (This upper bound is proportional to (n^2/log n), not (n/log n) as stated in the summary.)

* I don't follow cubology that closely, so I'm taking their word for it that this is a new upper bound.

Re:General algorithm already known

[Mogusha]

It's not even a generalization. It's the exact same algorithms. Once you can solve a 4x4x4 there is no extra algorithms needed at all to solve any cubes of any higher degree.

The typical idea is to solve the cube to the point of being a 3x3x3 with all the centers and edges solved. When solving the edges if you're trying to get the edges in place any portion of the edges can be grouped to look like a cube with a smaller degree.

Someone could argue that the 5x5x5 and 4x4x4 algorithms are needed, because of the extra center edge pieces, but with proper edge pairing that's usually a moot issue. But, I could always be wrong, the 4x4x4 and 5x5x5 algorithms might be needed for any cube larger than a 3x3x3. The real point is that anything above a certain point is the exact same algorithms.

Re:General algorithm already known

[kallisti]

Reducing to a size 3 cube is only one way of solving the cube. It has the drawback of a parity error where your reduced 3 cube can't be solved by using standard methods. For instance, on a size 4 cube you can get to a position where two adjacent edge pieces are swapped and inverted, as if the size 3 cube had one edge flipped, which is impossible. You can also have two corners swapped. There are some known moves to fix these errors, and most (all?) speed cubers use reduce-to-3 so it isn't a major problem. But there are at least two new algorithm required to solve bigger cubes than 3 using this method.

Now, if you don't use reduce-to-3, then you can solve any size cube with just 3 algorithms: one to cycle 3 edges with flipping, one to cycle 3 corners and one to swap center pieces, which are actually very easy because there are always 4 of them that look identical. The really trippy part is that this method was expanded to work on 4 and 5 dimensional cubes, too.

Patent Pending

[cultiv8]

This system and method for solving a Rubik's cube is a social media networking plug-in widget that synergizes, optimizes, and rightsizes the Rubik cube solving experience, utilizing HTML5/CSS3/JS code in a novel and innovative way to provide end-users with a single, solidified and parsimonious User Interface (UI), optimized for the User Experience (UX), utilizing Information Architecture (IA), over 256bit SSL security. It is built on a 100% cloud-based, distributed OS, independent architectural framework and uses the actual "internet" to facilitate communication between said end-user's "keyboard", to our proprietary "software", and back to end-user's "monitor".

The solution?

[tool462]

-After the researchers solve the 3x3x3-

Buttercup: We'll never succeed. We may as well die here.

Westley: No, no. We have already succeeded. I mean, what are the three terrors of the General Cube Solution? One, the pieces coming off - no problem. There's a popping sound preceding each; we can avoid that. Two, the stickers peeling off, which you were clever enough to discover what that looks like, so in the future we can avoid that too.

Buttercup: Westley, what about the R.O.U.S.'s?

Westley: Rubik's Of Unusual Size? I don't think they exist.

-- Immediately, Westley is attacked by a 4x4x4 cube --

Re:This can lead to impossible cubes

[Trunklebob]

White is opposite yellow. Blue is opposite green. Are you sure you hadn't just forgotten how to solve a Rubik's Cubes?

White/yellow is the Western color scheme; White/Blue was more common in Japan, but I've had one or two of them here in the States, too.

http://www.speedsolving.com/wiki/index.php/Japanese_Color_Scheme

It's time for Slashdot to support Unicode properly

[eobanb]

Lack of support for 20 year-old standard is usually just annoying as hell, but in this case it's actually caused the summary to be wrong. For a site that frequently discusses such topics as technology, math and language (for all of which Unicode is an important part—at least insofar as even being able to TALK about these subjects) there is absolutely no excuse for not doing Unicode.

As far as I'm concerned Slashdot ought to be able to render MathML too.

Mr Rubik

[pinballer]

I could only ever manage to get 5 out of the 6 sides :(

What about a 3x3x3x3x3 "cube"?

[Rich0]

It seems boring to me to just extend the size in 3 dimensions. What about extending it beyond three dimensions?