Of course that would still be the case if there were no Hamiltonian circuit. The only new thing that brings is that the number of moves to solve it is less than the number of possible configurations.
If you did a trillion moves per second then it would take around a billion years. Top speed cubers make around 25 moves a second, so even at that top human rate you're looking at using around 40 billion billion years.
This is neat, though it's from 2012 or maybe earlier.
I wonder if there is a single not-too-long rotation sequence that generates the whole cube group. That is, a sequence XYZ that you can perform repeatedly and have that bring you through every cube state. If not, maybe there is some other very simple algorithm that traverses all the states, instead of a zip file that uncompresses to 200MB.
But the question here is not looking for a generator, because it would be okay if some group elements are only reached during the application of the sequence. (For the sequence to be a generator, all group elements need to be reached at the end of some full application of the sequence.)
The Hamiltonian cycle sequence from the original post is not a generator, but it visits every state. The question is: Is there a significantly shorter sequence that (when repeated) does the same?
We can give a concrete example that non-Abelian groups can satisfy this with S_3, which is the smallest non-Abelian group. Swap the first two elements; then swap the last two. Repeat three times. You get the sequence
Wikipedia (citing a book on archive.org but no page number) [1] claims the largest order of an element of the Rubik's cube group is only 1260, so the simple repetition strategy would have to have a repeated unit way too long to be practical. (It sounds like you could potentially get a longer sequence if you allow "rotating the cube" as a move vs just turning the sides, though probably not enough to matter)
The linked circuit does have a repeating pattern like this at its core, and visits entire cosets of a subgroup at a time (presumably the same way each time) so it seems like there's already a bit more structure than a random 200MB file.
This is up there in "performance art" because the robot would take forever. Mitsubishi apparently has a robot that can do a normal cube solve in ~0.3 seconds (https://www.livescience.com/technology/robotics/this-ai-powe...), which they developed to show off their precision manufacturing. They mention one run that did 15 moves in 0.204 seconds. At that rate it works out to ~19 billion years to run through all positions.
Don’t forget leap years! What’s 18.6 billion years between friends?
I’m sure they could make it go faster but I suspect the reason the robot works at this speed is the friction in the cube only raises the temperature a few degrees before the cube settles and can cool down. And pausing for 60 milliseconds so the human eye has time to register the cube positions probably doesn’t suffice.
You could probably get it down to a billion years without reducing it to just a blur. A couple million if you point a bunch of high speed cameras at it and show the last fifty moves on screens next to the machine. Or 30 machines all showing 1/30th of the cycle.
Bit of a meta note: grown adult here who never got into cubing earlier in life. Recently picked one up as some non-screen entertainment for some long haul flights and train travel. Highly recommend.
Same here! I recently picked up a cube after a lifetime of thinking that I didn’t enjoy this kind of puzzles. A couple months have passed, and I carry the cube everywhere I go as I work on getting my time below 30s.
If you’ve got disposable income (and you might if you’re here), I highly recommend getting a pro-level cube. Even the fanciest ones don’t go above $60 or so, and it’s a lot more fun to play with a cube that glides on auto-aligning magnets than it is to fight a poorly-built piece of plastic that keeps locking up.
Fellow adult who also started late, also would recommend! Quite soothing activity. Using the abacus gets me in a similar way too, even though it's not a puzzle specifically. Something about the tactile focus and modest brain activity is pleasant.
For anyone wondering what an illegal cube scramble looks like, you can rotate one of the corners or edge pieces in-place, on the more forgiving cube designs. This renders the cube unsolvable (via regular legal moves) until you revert the illegal move(s).
For some reason that I can't explain that reminded me of a diabolical trick someone once did on the 15 puzzle [1].
They made a 15 puzzle where instead of numbers the tiles had letters on them, and the goal was to make a particular sentence. That sentence had 13 letters that appeared once and one letter that appeared twice.
That letter that appeared twice was the first letter of the sentence, and its other appearance was at or near the end. Let's call the two tiles with the same letter T1 and T2, where T1 is the tile that is the tile that is first.
They would show someone the solved puzzle, then scramble it, and challenge the person to solve it. When they were scrambling it they made sure to move T2 to the first position and T1 to somewhere near the end.
Nearly everyone who tried to solve it would see the right letter at the first position and never move it, because most people try to solve left to right and/or top to bottom.
On the 15 puzzle exactly half of the possible permutations of the 15 tiles are reachable from a given starting position. Exchanging two tiles in a reachable permutation produces an unreachable permutation.
That means that the right sentence but with T1 and T2 swapped is not reachable and so people who left T2 in front were doomed to failure.
The same thing can happen on some Rubik's cuboids - it seems unsolvable with a parity problem, then the answer is to swap two seemingly identical elements.
I know it happens on the 3x3x4 cuboid - each of the 3x4 faces has two centers that appear identical, but if you have exactly two such unsolved pieces, it's unsolvable because it's impossible to exchange exactly two of them - what you need to do is cycle 3 of them where 2 appear identical. I remember this happening on some other shapes and sizes as well.
If memory serves, it also happens with the hollow 3^3 cube, because there’s a translation of the center which also pulls two of the edges with it. And since you can’t see the center you don’t realize you fucked up until you’re solving the top face and something is wrong.
One of my coworkers years ago, a Rubik's fan, got a job once in small part because he solved a cube in the boss's office and pointed out that someone was fucking with him by rotating one of the edges 180º, making it unsolvable.
Happened to me like last week (not in my boss's office though). The person couldn't find out why they could no longer solve the cube. I realized someone else had turned a corner 180° when I recognized an impossible configuration. I solved it easily afterwards.
> The person couldn't find out why they could no longer solve the cube.
If you got to the point where you can routinely solve cubes, i.e. you know your algorithms or you developed a good intuition, then unsolvable cubes should be pretty obvious. Some algorithms are like: if you are in this position, do this, if you are in that position, do that, other positions are illegal. If you are in an illegal position, then you know there is a problem with your cube.
The Rubik's cube is a really hard puzzle unless you know some theory, and the existence of unsolvable cubes is a rather well known fact, meaning that there shouldn't be that many people who are able to solve the cube and don't know about unsolvable cubes.
Or maybe that's just me. I learned on a terrible cube that had a tendency to dismantle itself, so knowing that it had to be put back properly was a requirement for a successful solve.
The fact that the number of positions a cube could be in is greatly curtailed by the limitations of how many positions an assembled cube can transition to was not widely known information for a long time. When I relearned to cube it was news to me. If you haven’t touched a cube in twenty years you might not know.
My intuition when reading the first lines of this article was that, just like when searching exhaustively for the correct combination on a padlock, one would cycle through each subgroup, where each of them would represent a digit on the lock. On the lock, one would do 9 steps (not 10, as this would loop the lock to a previously seen combination) on the least significant digit, then propagate the carry to the next digits. But it seems that this more complicated than that, as the steps at which subgroups connect (the carry) are not always the same?
Clearly that first intuition doesn't work. The Hamiltonian cycle for decimal numbers is perhaps an equivalent of grey code? And if it exists, is there a connection with the Rubik's cube cycle?
The reason why it's not so simple is that various operations on the cube do not commute (whereas rotations of different wheels on a combination lock do).
Yes indeed, I realized that it was way more complicated than what I initially imagined.
When I first read the article, the sequence of subgroups that were described evoked that image of a combination lock to me:
< UR >
< U, R >
< U, R, D >
< U, R, D, L >
< U, R, D, L, F >
The behavior of the basic operations on the cube reminds me of the product of quaternion base vectors (i,j,k). For instance, the product of i and j would yield either k or -k depending on the order of i and j. I think the point I wanted to make is that on a combination lock, each operation on a wheel only affect that wheel, not the others, so one cannot produce another operation by combining several of them, like what we see with quaternions. However, on the cube, it is often possible to go from one combination to another by different sequences of different operations.
But that may not matter much, if all we care about is going through every possible combination exactly once, just like what one does when using gray code on binary numbers (which is why I alluded to that in my other post), and that for that purpose we can find a set of sequences of operations - let's call them large operations - that are orthogonal (and thus emulating the rotating wheel aspect of the combination lock). I suppose that these subgroups represent the large operations. The problem you bring up now is that these large operations are not commutative, and so finding a correct way to apply them to build the circuit is more involved than simply spinning the wheels on a lock.
Is that correct?
Edit: I just had a first look at cayley graphs on wikipedia, and they use quaternion rotations as an example!
FYI, it would take approximately 99.3 billion years to complete the Hamiltonian circuit of the Rubik's cube’s quarter-turn metric Cayley graph using the GAN 12 Maglev UV Coated 3x3 Rubik's cube.
You can solve a (legally scrambled) Rubik's Cube with no knowledge of its initial state, as long as someone stops you when you've done it.
You also need several billion years to do this, so it's not recommended for beginner solvers.
Of course that would still be the case if there were no Hamiltonian circuit. The only new thing that brings is that the number of moves to solve it is less than the number of possible configurations.
If you did a trillion moves per second then it would take around a billion years. Top speed cubers make around 25 moves a second, so even at that top human rate you're looking at using around 40 billion billion years.
I'll never see this scene from UHF quite the same way again:
https://www.youtube.com/watch?v=TYM4QKMg12o
This is neat, though it's from 2012 or maybe earlier.
I wonder if there is a single not-too-long rotation sequence that generates the whole cube group. That is, a sequence XYZ that you can perform repeatedly and have that bring you through every cube state. If not, maybe there is some other very simple algorithm that traverses all the states, instead of a zip file that uncompresses to 200MB.
If there were a single element that generated the whole group, the group would be abelian.
But the question here is not looking for a generator, because it would be okay if some group elements are only reached during the application of the sequence. (For the sequence to be a generator, all group elements need to be reached at the end of some full application of the sequence.)
The Hamiltonian cycle sequence from the original post is not a generator, but it visits every state. The question is: Is there a significantly shorter sequence that (when repeated) does the same?
We can give a concrete example that non-Abelian groups can satisfy this with S_3, which is the smallest non-Abelian group. Swap the first two elements; then swap the last two. Repeat three times. You get the sequence
123, 213, 231, 321, 312, 132, 123
I think we can go even further than that? If a single element generates the whole group, doesn't that mean the group is cyclic?
Wikipedia (citing a book on archive.org but no page number) [1] claims the largest order of an element of the Rubik's cube group is only 1260, so the simple repetition strategy would have to have a repeated unit way too long to be practical. (It sounds like you could potentially get a longer sequence if you allow "rotating the cube" as a move vs just turning the sides, though probably not enough to matter)
The linked circuit does have a repeating pattern like this at its core, and visits entire cosets of a subgroup at a time (presumably the same way each time) so it seems like there's already a bit more structure than a random 200MB file.
https://en.wikipedia.org/wiki/Rubik%27s_Cube_group#Group_str...
A bogosort for Rubik's cubes would be excellent. Especially if someone makes a robot.
This is up there in "performance art" because the robot would take forever. Mitsubishi apparently has a robot that can do a normal cube solve in ~0.3 seconds (https://www.livescience.com/technology/robotics/this-ai-powe...), which they developed to show off their precision manufacturing. They mention one run that did 15 moves in 0.204 seconds. At that rate it works out to ~19 billion years to run through all positions.
Don’t forget leap years! What’s 18.6 billion years between friends?
I’m sure they could make it go faster but I suspect the reason the robot works at this speed is the friction in the cube only raises the temperature a few degrees before the cube settles and can cool down. And pausing for 60 milliseconds so the human eye has time to register the cube positions probably doesn’t suffice.
You could probably get it down to a billion years without reducing it to just a blur. A couple million if you point a bunch of high speed cameras at it and show the last fifty moves on screens next to the machine. Or 30 machines all showing 1/30th of the cycle.
you mean you want the algorithm that generated the 200MB explicit recipe?
wouldn't that be the very paper that's shared as article here?
No I want a much simpler algorithm, with just a few bits of state, say.
Bit of a meta note: grown adult here who never got into cubing earlier in life. Recently picked one up as some non-screen entertainment for some long haul flights and train travel. Highly recommend.
Same here! I recently picked up a cube after a lifetime of thinking that I didn’t enjoy this kind of puzzles. A couple months have passed, and I carry the cube everywhere I go as I work on getting my time below 30s. If you’ve got disposable income (and you might if you’re here), I highly recommend getting a pro-level cube. Even the fanciest ones don’t go above $60 or so, and it’s a lot more fun to play with a cube that glides on auto-aligning magnets than it is to fight a poorly-built piece of plastic that keeps locking up.
Fellow adult who also started late, also would recommend! Quite soothing activity. Using the abacus gets me in a similar way too, even though it's not a puzzle specifically. Something about the tactile focus and modest brain activity is pleasant.
For anyone wondering what an illegal cube scramble looks like, you can rotate one of the corners or edge pieces in-place, on the more forgiving cube designs. This renders the cube unsolvable (via regular legal moves) until you revert the illegal move(s).
For some reason that I can't explain that reminded me of a diabolical trick someone once did on the 15 puzzle [1].
They made a 15 puzzle where instead of numbers the tiles had letters on them, and the goal was to make a particular sentence. That sentence had 13 letters that appeared once and one letter that appeared twice.
That letter that appeared twice was the first letter of the sentence, and its other appearance was at or near the end. Let's call the two tiles with the same letter T1 and T2, where T1 is the tile that is the tile that is first.
They would show someone the solved puzzle, then scramble it, and challenge the person to solve it. When they were scrambling it they made sure to move T2 to the first position and T1 to somewhere near the end.
Nearly everyone who tried to solve it would see the right letter at the first position and never move it, because most people try to solve left to right and/or top to bottom.
On the 15 puzzle exactly half of the possible permutations of the 15 tiles are reachable from a given starting position. Exchanging two tiles in a reachable permutation produces an unreachable permutation.
That means that the right sentence but with T1 and T2 swapped is not reachable and so people who left T2 in front were doomed to failure.
[1] https://en.wikipedia.org/wiki/15_puzzle
The same thing can happen on some Rubik's cuboids - it seems unsolvable with a parity problem, then the answer is to swap two seemingly identical elements.
I know it happens on the 3x3x4 cuboid - each of the 3x4 faces has two centers that appear identical, but if you have exactly two such unsolved pieces, it's unsolvable because it's impossible to exchange exactly two of them - what you need to do is cycle 3 of them where 2 appear identical. I remember this happening on some other shapes and sizes as well.
(Pic for reference: https://www.grubiks.com/images/puzzles/30/small.png . This puzzle exists as do many other NxMxH cuboids. Rectangular but non-square faces can only make 180º turns.)
If memory serves, it also happens with the hollow 3^3 cube, because there’s a translation of the center which also pulls two of the edges with it. And since you can’t see the center you don’t realize you fucked up until you’re solving the top face and something is wrong.
Heh… that exact situation came up here a few years ago, when someone posted their software implementation of the puzzle:
https://news.ycombinator.com/item?id=10540014
That's eeeeevil.
Wow - that is fiendish!
One of my coworkers years ago, a Rubik's fan, got a job once in small part because he solved a cube in the boss's office and pointed out that someone was fucking with him by rotating one of the edges 180º, making it unsolvable.
Happened to me like last week (not in my boss's office though). The person couldn't find out why they could no longer solve the cube. I realized someone else had turned a corner 180° when I recognized an impossible configuration. I solved it easily afterwards.
> The person couldn't find out why they could no longer solve the cube.
If you got to the point where you can routinely solve cubes, i.e. you know your algorithms or you developed a good intuition, then unsolvable cubes should be pretty obvious. Some algorithms are like: if you are in this position, do this, if you are in that position, do that, other positions are illegal. If you are in an illegal position, then you know there is a problem with your cube.
The Rubik's cube is a really hard puzzle unless you know some theory, and the existence of unsolvable cubes is a rather well known fact, meaning that there shouldn't be that many people who are able to solve the cube and don't know about unsolvable cubes.
Or maybe that's just me. I learned on a terrible cube that had a tendency to dismantle itself, so knowing that it had to be put back properly was a requirement for a successful solve.
The fact that the number of positions a cube could be in is greatly curtailed by the limitations of how many positions an assembled cube can transition to was not widely known information for a long time. When I relearned to cube it was news to me. If you haven’t touched a cube in twenty years you might not know.
You can't turn a corner 180°.
Did you mean flip an edge, or 120°?
Sure you can. It will just stick out a bit :P
<crunch> see I fixed it!
My intuition when reading the first lines of this article was that, just like when searching exhaustively for the correct combination on a padlock, one would cycle through each subgroup, where each of them would represent a digit on the lock. On the lock, one would do 9 steps (not 10, as this would loop the lock to a previously seen combination) on the least significant digit, then propagate the carry to the next digits. But it seems that this more complicated than that, as the steps at which subgroups connect (the carry) are not always the same?
Clearly that first intuition doesn't work. The Hamiltonian cycle for decimal numbers is perhaps an equivalent of grey code? And if it exists, is there a connection with the Rubik's cube cycle?
The reason why it's not so simple is that various operations on the cube do not commute (whereas rotations of different wheels on a combination lock do).
Yes indeed, I realized that it was way more complicated than what I initially imagined.
When I first read the article, the sequence of subgroups that were described evoked that image of a combination lock to me:
< UR >
< U, R >
< U, R, D >
< U, R, D, L >
< U, R, D, L, F >
The behavior of the basic operations on the cube reminds me of the product of quaternion base vectors (i,j,k). For instance, the product of i and j would yield either k or -k depending on the order of i and j. I think the point I wanted to make is that on a combination lock, each operation on a wheel only affect that wheel, not the others, so one cannot produce another operation by combining several of them, like what we see with quaternions. However, on the cube, it is often possible to go from one combination to another by different sequences of different operations.
But that may not matter much, if all we care about is going through every possible combination exactly once, just like what one does when using gray code on binary numbers (which is why I alluded to that in my other post), and that for that purpose we can find a set of sequences of operations - let's call them large operations - that are orthogonal (and thus emulating the rotating wheel aspect of the combination lock). I suppose that these subgroups represent the large operations. The problem you bring up now is that these large operations are not commutative, and so finding a correct way to apply them to build the circuit is more involved than simply spinning the wheels on a lock.
Is that correct?
Edit: I just had a first look at cayley graphs on wikipedia, and they use quaternion rotations as an example!
FYI, it would take approximately 99.3 billion years to complete the Hamiltonian circuit of the Rubik's cube’s quarter-turn metric Cayley graph using the GAN 12 Maglev UV Coated 3x3 Rubik's cube.