20 May 2008

Large Rubik's cubes and asymptotic thoughts

A video of the solution of a Rubik's cube of side 100, from YouTube.

I don't know the details of the algorithm, but it has the interesting property that at first it looks like nothing's happening, and then larger and larger blocks of each color seem to form -- I'm not sure if this is because of the low resolution or if this really is some sort of "phase transition" in the algorithm. This is the sort of thing one just doesn't see in the normal-sized cube.

I came to this from a solution of the size-20 cube, which works in a much different way; each of the faces of the cube gets "filled in" in turn. So in the second case the algorithm appears to be making steady progress; in the first case it doesn't. There are essentially two different families of algorithm.

It would be interesting to know how the solution time (measured in number of moves) of these families of algorithms -- and I'm calling them "families" because I suspect that the actual side length of the cube isn't all that important -- scales with time. Also, how do these algorithms compare with the asymptotically fastest one? One could compute a lower bound on the number of moves needed to solve a Rubik's cube of arbitrary size by just computing the number of possible positions (analogously to the calculation of that number for the normal cube I outlined here) and comparing that to the number of possible moves one can make from a given position. An absolutely useless question -- is that lower bound (I worked it out once, but I forget what it is, and it was the sort of the back-of-the-envelope work that might have been wrong anyway) asymptotically tight? That is, does there exist a solution procedure for the Rubik's cube for which the number of moves needed to solve the size-n cube is within a constant factor of this obvious lower bound?

As for what that lower bound is, I may write that up as another post; I'd either need to find the notes I made on it a few months ago or (more likely) rederive them.

Anonymous said...

I keep averting my eyes from any mention of solving a Rubik's Cube, because I want to figure it out myself before I seen anyone else's solution, but I don't suppose looking at the 100-side solution in action will do any harm.

Buddha Buck said...

When talking about general algorithms for cubes, parity matters -- cubes of size 2n are different than cubes of size 2n+1. Cubes of odd order have fixed centers and have an orbit of 12 edge pieces in which piece orientation is important. Cubes of even order have no fixed centers and their edge pieces fall into orbits of 24 edge pieces each where each piece has a single permissible orientation. Cubes of odd order 5 or greater have both issues, but they can be treated independently.

My solution for the general cube isn't fast, but it gets me there. Basically, for a cube of size 2n there is 1 orbit of 8 corner pieces, (n-1) orbits of 24 edge pieces, and (n-1)^2 orbits of 24 center pieces. I essentially solve the cube in that order -- corners, edges, centers -- and by far the longest to solve is the centers, as I solve each center piece (all 24(n-1)^2) individually in the worse case. There is some flexibility, as the 24 center pieces in each orbit fall into 6 groups of 4 indistinguishable pieces.

Anonymous said...

I know that the in-video commentary says it's not, but I'm actually sort of tempted to say it's a reverse scramble. Yes, I know there are general algorithms, but the end stages of this look really random compared with the algorithms I know.

This "structure appears from nowhere" stuff actually shows up in Thistlethwaite's algorithms for the 3x3x3 cube, but that one has been extensively tweaked by hand. I find myself really doubtful that anyone's hald-tweaked a 100x100x100 algorithm like that.

Anonymous said...

Could someone explain how "I'm going to do a few more moves to prove it's not a reverse scramble" is meant to work?

(I could see the point if *someone else* chose the "random" moves)

Anonymous said...

I think it means that he's trying to do something that wouldn't happen if the video were reversed.

Anonymous said...

Well, he did it within the program that I presume he wrote. Like we're supposed to just trust him that it's not capturing the moves?

I'm not an expert on Rubik's cube algorithms, but I agree that it looks like a reverse scramble. Still, couldn't it be a heuristic? Group enough of the squares together, then treat it like a 10x10x10? (Or any other factor of 100.) It's hard to tell if that's what is happening in a video with such low resolution.

CarlBrannen said...

Another vote for the reverse scramble, but I don't have a dog in this fight and really don't care.

My first cube was a 3-cube, of course, and I ended up with a pile of difficult to remember arbitrary moves. A lot of them involved 180 degree moves.

Later, I got more general cubes that have x3 or x5 rotations. These do not have 180 degree moves. As a result of solving them, I ended up with a very small number of rather inefficient but extremely easy to remember commutators.

Basically, I only have two moves, A B /A /B and A /B /A B and then commutators of commutators where A and B are 90 degree rotations. I do the faces first, then the edges, and finally the corners. This generates some difficulties, particularly with the 4x4 cube because of parity stuff, but it is very efficient with 5x5 cubes.

Anonymous said...

He doth protest too much. Absolutely, positively, beyond a shadow of a doubt, it's a reverse scramble. The "order-out-of-chaos" thing is a dead giveaway, even if it weren't for the fact that I highly, highly doubt any algorithms exist for solving a 100x100 cube in so few moves.

Michael Lugo said...

Brent,

there's no move counter, so I don't know if you can say there could be no algorithm to solve in that few moves.

But I looked a little more closely at the video -- and it looks like the "algorithm" starts out by reversing the very moves which were used to show that it's not a reverse scramble!

Anonymous said...

> it looks like the "algorithm" starts out by reversing the very moves which were used to show that it's not a reverse scramble!

Then it's worse than I thought -- I had assumed the "random" moves would just be the first few moves of the reverse scramble.

Kevin Roberge said...

Its not a human solve. The poster isn't claiming to have solved it. It would be slightly pointless to show a 'computer solve' that was actually a reverse scramble, what would the motive be?