Slashdot Mirror
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."
I suppose I should inform my parents or lack of a girlfriend or something...
That's an easy solution.
It's n^2/log n.
My
Isn't giving all 3 dimensions a little redundant if you're specifying that it's a cube?
Does it scale to >3 dimensions?
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.
There's no -1 for "I don't get it."
MY youngest brother is 11 and he can do rubik's cubes up to a 7x7.
Crazy. And unlikely of ever getting laid.
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 opposite sides.
For all intensive purposes, "whom" is no longer a word. That begs the question, "who cares"?
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.
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.
Quattuor res in hoc mundo sanctae sunt: libri, liberi, libertas et liberalitas.
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".
sysadmins and parents of newborns get the same amount of sleep.
-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 --
I once solved a 1x1x1 rubik's cube! ;-;)
(I cheated and took the stickers off
Has someone notified the Borg?
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.
Take off every sig. For great justice.
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...
I could only ever manage to get 5 out of the 6 sides :(
It seems boring to me to just extend the size in 3 dimensions. What about extending it beyond three dimensions?
You know what else should work? When they change the UI, it should ruin such things like being able to actually click links in comments.
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.
Is it a secret? I couldn't find it linked off of or within the article.
Step 1: Remove all stickers
Step 2: Reapply stickers of one color to one face of cube
Step 3: Repeat step 2 with remaining colors/faces
What's so hard about that?
Unfortunately fixing text encoding issues would do nothing about the leading cause of incorrect summaries around here, better known as "slashdot editors".
The article says "the maximum number of moves that will ever be required for a cube of side n is proportional to n^2/logn". It also says "standard Rubik's cube can be solved in 20 moves or less" and then it says Demaine's "first task is to work out how to turn that into an exact number for given sizes of cube." but if the number of moves for n=3 is 20 and the number of moves is proportional to n^2/logn then the number of moves for cubes of any length =kn^2/logn where k=20/(3^2/LOG(3)) = 1.1 . So maximum number of moves = 1.1 n^2/logn (approximately) and Demaine's first task is completed unless he needs exact numbers for each n.
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 characters together followed with a normal character (some strange millions-comma thing).
And it's a pain in the butt, too - you can't search for it, certain operations destroy the characters, so you get very strange behavior.
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
"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 second overlapping phase was inspired by the symmetric of the DNA or RNA double helix, presumed that life must necessarily be based on some form of template replication of one strand by ligation of free nucleotides to create the second strand, melting of the two strands and cycling again. Spearheaded by L. Orgel, but with many others, this effort has, to date, failed. The third phase begins with the discovery that RNA molecules can act as enzymes, and posited the RNA world, in which RNA molecules dominated. This has led to slightly successful efforts to evolve an RNA sequence able to template replicate itself. Current success is an evolved ribozyme able to do so for 14 nucleotides."
How can the Demaines not do better than those CERN guys, where "The author has gathered some 17 scientists from around the world to collaborate and compete with one another, CERN/LHC experiments style, in a generative scientific environment."? It was after all a folding competition, wasn't it...
But shouldn't there be some decent libraries that filter control characters? You might just allow a few more planes than Basic Latin...
UTF-8 is ASCII-compatible, why shouldn't it be possible to search for it?
If one can solve the 3x3, 4x4 and 5,5 it's relatively simple to solve any sized cube by splitting it into overlapping subcubes and expanding the algorithms. The only real thing, is time, it takes a lot of it.
take a move, revert it with the next move, repeat ad libitum. You get an infinite sequence of moves that does not ensure the reachability of the solution.
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 meaningless.
If they can't even manage to do basic counting, I fear there's bugger all chance they'll manage to do unicode any time soon.
Once you learn how to solve a 3x3x3, a 4x4x4 and a 5x5x5, Everything else is just a few modifications of the same algorithims used. This algorithim has been around for years and the fact that someone took time and money to develop this again is quite worrying.
i'm not the only one...!? wtf slashdot...? i really don't get all the constant UI changes. some have brought mild improvements, and that's cool. but the recent ones have just brought bug after bug, with often negligible gain. who seriously thinks the site needs all these updates?
It's a fucking CUBE, why do you need to specify the size of all the dimensions? One dimension is enough for crying out loud. Do you really think you can have a 3x4x5 cube?!
A general algorithm has existed for a long time. What the fuck.
"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?
Anyone knows solving a Rubik's cube is impossible.
Actually I may be lying, I believe the one-sized Rubik's cube may be solved for at least dimension 2.