## Algorithm Solves Rubik's Cubes of Any Size 139

Posted
by
timothy

from the gordian-knot-sledgehammer dept.

from the gordian-knot-sledgehammer dept.

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."*
## From TFA... (Score:3, Informative)

It's n^2/log n.

## Re:From TFA... (Score:5, Informative)

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... (Score:5, Funny)

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: (Score:1)

That wouldn't imply that anyways since we're talking asymptotics here. It doesn't say anything about how fast you can solve a specifically sized cube, only the relationship between the difficulties in solving different sized ones.

## Re: (Score:2)

That's not how big O notation works. If something is O(

n) it doesn't mean that it can be solved inncalculations. It means it can be solved in C*n+D calculations, where C and D are constants.## Re: (Score:2)

## Re: (Score:1)

Well, for a sufficiently general definition of "move", each cube is solvable in a single move. :-)

## Re: (Score:3)

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

## Re: (Score:2)

## Re: (Score:1)

## Re: (Score:1)

## Is that base ten or base e? (Score:2)

In the latter case, log 3=1.09, and 11.9/1.09=10.9. . . Although the article says the upper bound is proportional to n^2/log n.

## Re: (Score:2)

## Re: (Score:1)

When talking about computational complexity, fixing a base of the logarithm makes no sense at all. Changing base just means a constant factor, and constant factors are ignored for complexity considerations.

## Re: (Score:2)

notation, that does not mean that they are irrelevant in computational complexity. Base matters, and constants matter.## Re: (Score:2)

Not according to Wikipedia http://en.wikipedia.org/wiki/Logarithm_of_the_base_2 [wikipedia.org].

In any case, log_2 3 = 1.584. . . and 11.9/1.584 is about 7.5.

## Yes, but... (Score:3, Interesting)

Does it scale to >3 dimensions?

## Solving != best solution (Score:1)

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.

## Re: (Score:2)

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: (Score:2)

A Rubik's cube has a finite number of states and a finite number of moves. So I don't understand how performing infinite moves wouldn't eventually result in the solution.

## Re: (Score:1)

## Re: (Score:2)

No. That's simply not true. If there is a 99% chance of you stepping *back* and a 1% chance of you stepping *forward*, the probability of you *eventually* reaching your house approaches 100%, eventually. The average time for you to reach your house, however, is really quite long.

## Re: (Score:2)

## Re: (Score:2)

You should probably qualify that a little... for example, any normal rubik's cube, or any rubik's cube that hasn't been tampered with, or something similar... it is actually very easy to make any rubik's cube completely and permanently unsolvable.

## Re: (Score:1)

it is actually very easy to make any rubik's cube completely and permanently unsolvable

Only if "make" involves operations that "solve" does not. For instance, a freight train can very easily "make" a Rubik's cube completely and permanently unsolveable.

## Re: (Score:2)

## Re: (Score:1)

My point was more that any cube in any position that can be reached by standard moves is solveable by those same standard moves. Obviously, rearranging stickers, disassembling the cube, or introducing outside forces (crazy glue, freight trains) can make the cube "unsolveable" by any possible combination of standard moves.

But that all begs the question: is a Rubik's cube still a Rubik's cube if it's been disassembled, modified, and/or re-assembled in a condition that would be impossible for a Rubik's cube to

## Well that's not good (Score:3)

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: (Score:1)

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.

hahahahahahahaha aaaaahhhhhhh

## Re: (Score:2)

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.

What's funny about this is that when I was in college, my roommate was obsessed with Rubik's cubes. He wrote a program to simulate an arbitrarily sized cube, and would then sit there and solve it. The largest I remember him doing was 42x42x42.

Your roommate is amazing. Anyway, after some deep contemplation I've gotten over the devastation I experienced when reading TFA. I shall now focus my efforts on my continuing efforts (12 years so far) to solve my 100 disk Towers of Hanoi puzzle that I've set up next to my bed in the basement. At least that should be solvable within a convenient amount of time, unlike the silly 60x60x60 Rubik's cube (what could I have been thinking?!) The cube is a bit cumbersome to use anyway as I constructed it out of wood

## Re: (Score:3)

## Re:Well that's not good (Score:4, Funny)

## Re: (Score:2)

He's fooling you. The number of twists needed to solve that would take years - longer if you're pointing and clicking with a mouse.

## General algorithm already known (Score:4, Informative)

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: (Score:2)

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

## Re: (Score:3)

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 proble

## Re: (Score:2)

## Patent Pending (Score:3, Funny)

## The solution? (Score:5, Funny)

-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 --

## solve (Score:1)

I once solved a 1x1x1 rubik's cube! ;-;)

(I cheated and took the stickers off

## The cube problem solved? (Score:2)

## It's time for Slashdot to support Unicode properly (Score:5, Insightful)

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.

## Re: (Score:2)

It did, at one point. The problem was the trolls went and ruined it for all of us by embedding all sorts of control characters in post that ended up destroying the flow of a web page and making the text unreadable.

Hell, I think most blogs probably aren't immune to the problem. There used to be one common indication of this because people would force 4 or 5 unicode control

## Re: (Score:2)

Agreed entirely.

Slashdot's codebase often feels like a joke to me. My own pet peeve is the discussion threshold slider - it's numbers are *never* correct. Right now on a different browser tab a discussion is saying there's "10 Full, 3 Abbreviated" - whereas it's actually displaying 7 full, and 0 abbreviated. Another is telling me "16 Full, 0 Abbreviated" - that one has the abbreviated count right, but there's only 6 comments visible. The numbers are often so wildly out that they're completely meaningles

## side n (Score:1)

required for a cube of side n

I don't even want to think about solving a cube with n sides. Not to mention, how a cube ever got n sides to begin with...

## Mr Rubik (Score:4, Funny)

## Re: (Score:2)

## Re: (Score:1)

## Re: (Score:2)

## Re: (Score:1)

## Re: (Score:2)

## Re: (Score:2)

## Re: (Score:2)

## What about a 3x3x3x3x3 "cube"? (Score:3)

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

## Re: (Score:2)

I think you could do this by having an array of cubes somehow interlinked... or http://www.superliminal.com/cube/cube.htm [superliminal.com]

## Re: (Score:2)

## Re: (Score:2)

Integral dimensions. Booooring. Solve me a fractal cube.

## Re: (Score:1)

Actually I really want to see a 3x3 version. i would also be interested in owning just a 3 if anyone has one.

## Demaine's first task is completed? (Score:1)

## The CERN life challenge (Score:1)

The Demaine father (Martin) and son (Erik) are a very impressive couple.

I congratulate both of them.

Let me suggest that they tackle "The current status of work on the origin of life" http://indico.cern.ch/conferenceDisplay.py?confId=137302 [indico.cern.ch]

"Work on the Origin of Life is poised to converge onto a fourth phase and, many of us hope, success. The first phase concerned prebiotic synthesis of the small molecules, amino acids, nucleotides, lipids and others, essential for life and spanned some forty years. The seco

## Already done! (Score:2)

## Re: (Score:2)

I used to charge people to solve their cubes for them back in grad

## Why need "x3x3?" (Score:2)

reallythink you can have a 3x4x5 cube?!## Sketchy Journalism (Score:2)

"Suppose someone takes a solved 20x20x20 Rubik's cube and makes five moves - can you figure out [from that scrambled state] what those five moves were?" he asks. In other words, can you solve it in five moves? He suspects that you cannot, but has yet to prove it. "We don't know."

Of course you can solve this cube in five moves--use brute force. It's getting little things like this wrong that makes me dislike journalists so much. If they misinterpret such an apparently simple comment, how wrong is the stuff I can't easily verify or refute?

## Re: (Score:1)

## Snake oil (Score:1)

## No (Score:1)

## Re: (Score:1)

## Re: (Score:2)

I can solve a Rubik's cube in less than 30 seconds. How long does it take to pull off the stickers and put them back on?

## Re: (Score:2)

## Re: (Score:2)

I used to do that too. Unfortunately the whole thing gets too loose if you pull it apart too many times.

## Re: (Score:2)

## Re: (Score:1)

## Re: (Score:1)

You really only need to pull off at most 48 of them.

## Re: (Score:2)

But then it would be no challenge.

## Re: (Score:1)

I see, the challenge is in remembering the position of the colors on the cube, to avoid someone detecting your cheating after the fact because two colors which were on opposite sides of the cube before now aren't.

## Re: (Score:3)

According to this [speedcubing.com], 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: (Score:3)

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

## Re: (Score:2)

He's trying to be 'funny' by saying he does it by pulling the stickers off.

(I bet it takes longer than 30 seconds though...)

## Re: (Score:2)

I can do it in under a 90 seconds sometimes (and under 60 seconds consistently when I was a kid), and i'm nowhere near the fastest person I know at solving them. 30 seconds isn't unreasonable for someone who is actually good at it.

## Re: (Score:2)

I used to do it in 30 seconds back in the '80s but last time I tried on it took more like a minute.

There's quite a few people out there who can do it in about 15 seconds average using newer methods. That's probably about the limit for humans.

If you see times lower than that it's because somebody got lucky on one particular solve. Sometimes the pieces just fall into place. I once did it in 19 seconds in front of a crowd of people but it was mostly luck (not that I told anybody that at the time...)

## Re: (Score:2)

Currently the record is a person averaging under 7s at the official competitions. I attended one once and saw a guy who averaged around 9s, most people competing (really competing) were around 10-15s, then there was me around 30s (just thought it'd be fun to try). The only girl who showed up to compete got around 2mins.

## Re: (Score:1)

Some people can do it under 60 seconds ... with their feet.

http://www.worldcubeassociation.org/results/e.php?i=333ft [worldcubeassociation.org]

## This can lead to impossible cubes (Score:2)

Back in the 80s when the cube was new and popular, I was really into it. IIRC, I got my times down under 3 minutes. Yeah, I know. Pretty pathetic by today's standards.

Anyway, somebody gave me a cube to solve once. After about 15 or 20 minutes it dawned on me that I had an impossible cube. Somebody who thinks they're moving closer to the solution by swapping stickers can do something like put the white sticker on a corner cubie with the blue sticker, not realizing that white and blue are always on oppos

## Re: (Score:1)

Anyway, somebody gave me a cube to solve once. After about 15 or 20 minutes it dawned on me that I had an impossible cube. Somebody who thinks they're moving closer to the solution by swapping stickers can do something like put the white sticker on a corner cubie with the blue sticker, not realizing that white and blue are always on opposite sides.

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

## Re: (Score:1)

White is opposite yellow. Blue is opposite green. Are you sure you hadn't just forgotten how to solve a Rubik's Cubes?In jr. high, I knew what I was doing. Now? I forgot which color was opposite which and didn't bother to google-check it.

## Re: (Score:2)

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 [speedsolving.com]

## Re: (Score:1)

Ah, so it's possible that my memory is not so flawed. I could have sworn blue was opposite white. Come to think of it, I do seem to recall that the colors were not rigidly standardized, and having seen what I thought were knock-offs. Maybe some of the Japanese cubes got sent to the US to meet demand, or I had an early cube made before the "Western" color scheme was adopted.

## Re: (Score:2)

I've seen both schemes...

## Re: (Score:2)

You can make a cube unsolvable just by rotating a single piece (eg not by completely disassembling it, just twisting one of the corners around). No amount of moving the cube around by the correct means can rotate only a single corner piece or flip a single edge piece - they have to be done in pairs or multiples of two.

## Re: (Score:2)

Built-in parity checking!

## Re: (Score:1)

## Re: (Score:2)

Only if you assume each cell is of the same dimension. You could very well have a cube that is 3x4x5 cells. Although it wouldn't work as a Rubik's Cube.

Back on topic.. I'm pretty sure I saw a 50x50x50 or something solved by software on YouTube.. is this algorithm bringing something new to the table, or...?

## Re: (Score:2)

Why can a cube not be composed of 3x4x5 cells so long a the cells are sized such that the cube is well, a cube?

## Re: (Score:2)

Why can a cube not be composed of 3x4x5 cells so long a the cells are sized such that the cube is well, a cube?

Because when you try to rotate the five-cell face, e.g., you'll be trying to move some of the cubelets from the four-cell face to the 3-cell face and vice versa. You'll have four cells trying to match up to 3 cells and vice versa. That may work, but if you then try to rotate the four-cell face, you'll be trying to move fractional cubelets.

Personally, I'll be impressed when the algorithm handles 50x50x50x50 Rubick's Hypercubes (patent pending).

## Re: (Score:2)

Draw a square. Now draw a line 1/3rd of the way along the horizontal axis parallel to the vertical axis. Draw another line 1/3rd of the way along the vertical axis parallel to the horizontal axis. You should now have a square that is divided into 1 smaller square, 1 larger square, and 2 equally-sized rectangles. Those rectangles aren't squares, true, but the outer square you began with is still a square.

Extrapolate that to a cube. Cut it up in any way you wish and each individually cut piece may not be

## Re: (Score:2)

Any piece which can be shifted into another piece's place has to be the same size and shape as the other piece, or it doesn't work right. Yours fails that.

Yes, I'm pretty sure we covered that when I initially said that it wouldn't work for a Rubik's Cube. I though it was made more obvious when Obfuscant explained that to somebody else, too ;) Thanks for the contribution, though

## Re: (Score:1)

## Re: (Score:2)

## Re: (Score:2)

Not to anybody with an IQ larger than their shoe size.