Rubik's Cubes

Fact I learned today: the question of whether an nxnxn Rubik's cube in a scrambled state can be solved in fewer than k moves is NP-complete. If you don't know or remember what it means to be NP complete, I wrote a post here in the math thread about it. Short version: if someone hands you a scrambled cube and tells you "here's how to solve it in fewer than k moves", you can verify that easily. But to figure out whether there is a solution in fewer than k moves is hard.
So there is a formal, mathematical sense in which solving a Rubik's cube is in fact hard, although like with many NP-complete problems, you're usually not looking at the general case so the NP-completeness is irrelevant.
This is an interesting problem, given that there is a method that will solve a Rubik's cube in O(n²/log(n)) time, i.e. there is some fixed positive constant C such that it never takes more than Cn²/log(n) moves to solve an nxnxn Rubik's cube. But telling whether a Rubik's cube can be solved in fewer moves than that is NP-complete.

 

Recently decided to pull out my Rubik's Cube whose solution attempts in the past I had always managed to flub near the end and I think I finally have the ability to properly follow the instructions. Of course, given that I actually work with groups and commutators, I now want to actually understand why the sequences of swaps work the way they do.

 

A void cube is like a standard Rubik's cube, except the faces and the central axes aren't there (the mechanism that allows it to turn without falling apart is quite clever and I'm not entirely sure I understand it.)
Most people, including myself, tend to use the center pieces as reference points; to say "I want all the yellow stickers to be around the yellow center piece" rather than, for instance, "around the yellow sticker on the yellow-green edge piece". Moreover, the center pieces provide a way to figure out where the colors should go relative to each other.
So, in the absence of such nice reference points, what can you do with a void cube?
One thing you can do is introduce "parity errors". You can make it appear that you have swapped two edge pieces, even though that is supposedly impossible on a standard Rubik's cube. The secret is that there's some extra turns there that would normally be visible due to the displacement of the center pieces, but without the center pieces, those extra turns are undetectable, so it looks like the entire cube is solved except for the two edge pieces.

 

My friend got me this for am early Christmas present. It turns super smoothly and I think the faces have a bit of grip on them, but mostly it just looks cool.

Spoiler: Big image

 

On any twisty puzzle, any algorithm that you can repeat will, if started from the solved position and repeated enough times, get you back to the solved state. How many repetitions depends on what the algorithm does.
In particular, you can break up what the algorithm does into cycles: if piece A ends up in position B, and piece B ends up in position C, and piece C ends up in position A, then you have a cycle (A -> B -> C -> A), which is a cycle of length 3. So you'd expect that if you perform the algorithm 3 times, then the piece A will end up back in position A and so on. Note that the cycle might actually be longer, since piece A might end up back in position A but twisted around, so you have to repeat more times. But the number of times will be a multiple of 3, since anything else will lead to piece A ending up in the wrong position.
If you had another cycle of length 5, maybe (D -> E -> F -> G -> H -> D) then you would have to perform the algorithm 15 times, so that both the ABC and the DEFGH cycles lined up. On the other hand, if you had a cycle of length 6, (Q -> R -> S -> T -> U -> V -> Q) then you wouldn't need to do things 90 times, but only 30, because 30 will fix both the length 3 ABC cycle and the length 6 QRSTUV cycle. It's because 3 and 6 have a factor in common, so we don't need to overcount that factor. The formal term is "least common multiple", i.e. the smallest number that is divisible by each of the cycle lengths, although not necessarily all at the same time. 30 is the least common multiple of 3, 5 and 6.

On the cube, there is a pretty basic algorithm where you pick a face, and then twist each of the faces adjacent to that face in order. So if you take the face as the front face, then you turn the upper face a quarter turn counterclockwise, then the right face counterclockwise, then the bottom face counterclockwise, and then the left face counterclockwise. Pretty simple, right?
This algorithm takes a decently long time to get back to the solved state, and passes through some interesting intermediate states as the various cycles align and misalign. There's a few 3-cycles, a 5-cycle and a 7-cycle and maybe some other stuff.

I recently got my hands on a Megaminx, which is like a Rubik's Cube but a dodecahedron instead of a cube.


In basically all other ways it's completely analogous, including a lot of the algorithms for solving it. You have to be careful when counting, though, because now a half turn counterclockwise is no longer the same as a half turn clockwise.

I tried the analogue of the above algorithm on the megaminx: a single turn on each face going in order around some fixed reference face. Since now the faces have 5 edges instead of 4, I expected to need roughly 5/4 as many repetitions.
I was quite a bit off, it turns out. Because not only does the 4 turn into a 5, but the 5-cycle also becomes a larger cycle, and the 7-cycle also becomes a larger cycle. So the least common multiple got boosted by all of those increases, leading to a much longer cycle with some very interesting subcycles.

Anyway I lost a decent chunk of time today to that discovery.

 

Awesome geek stuff. I can't focus on that sort of math stuff at the best of times... but when my husband even tries to go into that level of nerdiness, I remember why he's a keeper despite what the military did to him. (I was able to understand volume to radius exponents thanks to having https://goo.gl/images/xhekmr and playing a match-3 game.)

Would a 2x2 or a 1x3 be a good thing for a beginner who wants to learn how to actually try to make rubix cubes solved again? Last Christmas my nephew was using software to help him solve a 3x3, but I think he was also trying to figure out how to do it himself. I think I have a tiny 3x3 from a party store that makes a good fidget, but I can't find it. The last cheap cube I bought got returned because the mechanism was too rough.

 

People who learned how to solve a 3x3 first often found the 2x2 to be somewhat confusing at first, since it doesn't have the nice reference points that the 3x3 has.
I think that starting slowly on the 3x3 is the best thing to do. Start with solving one layer and then scramble and solve one layer and scramble again until you have that layer down cold, then move on to solving the first two layers and then scramble and then solve two layers and then scramble again until you get that down. You really need to have each step down before you can start leaning the next, because if you screw up you often have to start from the beginning.
Official Rubik's cubes are pretty decent these days in terms of movability if you want to get a new one.

 

I can't believe I forgot to link MagicTile before! It's a twisty-puzzle simulator, where the puzzle doesn't have to be topologically a sphere. How about a Rubik's torus? Or a Rubik's Klein bottle?

The idea is that all of the interesting information about a Rubik's cube is contained on the surface, and the interesting information is the coloring and how the various turnable layers intersect. So really you can model a Rubik's cube as a sphere with a bunch of intersecting circular cuts in it and the individual pieces colored in particular ways, and then you can ask what happens when you replace the sphere with something else.

Video of the Klein bottle:

 

Lately I've been playing with a Gear Shift, which looks like

when solved and looks like

when scrambled.

Each of the corners turns and the interlocking teeth cause neighboring corners to turn as well.
The interesting mechanism is that you can split the corners apart:

so that you can turn the left four corners independently of the right four corners. Similarly you can split the top four from the bottom four, or the front four from the back four.
The mechanism is set up so you can only do this splitting along one axis at a time, though.
The other interesting feature is that the smaller pieces have five teeth and the larger pieces have eight, so that the corners spin at different rates.
This discrepancy allows you to do things like

where only one corner is twisted and everything else is solved.

From a mathematical standpoint this object is actually really simple. It doesn't matter which order you perform moves in; the mathematical term is "abelian" or "commutative". If you turn the left four once and the top four once, that's the same as turning the top four once and the left four once.

There's a nice description of the basic moves:
We pair up the corners as an eight-tooth corner and the five-tooth corner opposite it. So our pairs look like
[(a₈, a₅), (b₈, b₅), (c₈, c₅), (d₈, d₅)]
And so the state of the cube can be written as eight numbers, describing how twisted each corner is from the solved position. Note that the eight-tooth corners twist from 0 to 7, since twisting by 8 tooth-turns gets you back to the beginning, and the five-tooth ones twist from 0 to 4, since twisting by 5 tooth-turns gets you back to the beginning. Mathematically this corresponds to dividing by 8 or 5 respectively and then taking remainders. So solved is
[(0, 0), (0, 0), (0, 0), (0, 0)]
while scrambled might look like
[(4, 2), (2,1), (7,3), (1,0)]
Then splitting and twisting by one tooth-turn is picking two pairs out of the four, adding 1 to the first entry in those two pairs and subtracting 1 from the second entry in the other two pairs, and then taking remainders.
So for instance, depending on how you ordered your corners, starting with the solved state and twisting the left four corners by one tooth-turn might look like
[(0, 0), (0, 0), (0, 0), (0, 0)] + [(1, 0), (1, 0), (0, -1), (0, -1)] = [(1, 0), (1, 0), (0, 4), (0, 4)]
and then twisting the front four corners by two tooth-turns might look like
[(1, 0), (1, 0), (0, 4), (0, 4)] + [(2, 0), (0, -2), (2, 0), (0, -2)] = [(3, 0), (1, -2), (2, 4), (0, 2)] = [(3, 0), (1, 3), (2, 4), (0, 2)]
and so on.
Of note is that five tooth-turns looks like adding
[(5, 0), (5, 0), (0, -5), (0, -5)] = [(5, 0), (5, 0), (0, 0), (0, 0)]
and eight tooth-turns looks like adding
[(8, 0), (8, 0), (0, -8), (0, -8)] = [(0,0), (0, 0), (0, 2), (0, 2)]
Combining the eight-tooth-turn moves can get you
[(8,0), (8, 0), (0, -8), (0, -8)] + [(0, 8), (-8, 0), (0, 8), (-8, 0)] + [(0, 8), (-8, 0), (-8, 0), (0, 8)] = [(8, 16), (-8, 0), (-8, 0), (-8, 0)] = [(0, 1), (0, 0), (0, 0), (0, 0)]
which is how we manage to twist a single corner.

 

The OpenAI people built a neural net that learns to solve a Rubik's cube using a robot hand that's articulated like a human hand. Most robots that solve Rubik's cubes have the algorithms for solving the cube preprogrammed, so here the interesting bit isn't so much the Rubik's cube as it is the neural net learning how to solve the thing based only on "how many colors are correct" and also in the presence of various types of interference. Learning the dexterity to manipulate a Rubik's cube is hard enough for people, who generally have a decent idea of how to make their hands do things. So the OpenAI team figured out how to get the neural net to be adaptable enough that it could deal with the team poking the cube with various things while the robot hand was trying to solve it.