> 2) I can place the first 11 edge pieces onto the cube any way I want. The orientation of the last edge piece is determined by the orientation of the first 11.
> 3) I need to track how many swaps I create by placing those pieces. An even number of swaps is solvable, and odd number is not.
Would it be equivalent to say, after placing the first 10 edge pieces, the position of the 11th is mandated, and then the orientation of the 12th is too? Or if (3) is broken might it be harder to fix than swapping the 11th and 12th?
But it introduces an artificial difference between edges and corners. You'd get the same ability for corners if you did them after the edges.
The slightly counterintuitive “magic” is that you can trade a corner swap for an edge swap: for permutation parity, corners and edges are interchangeable.
I loved reading this, but I can't help but think that a "perfect scramble" would be one that can ONLY be solved in 20 moves, i.e no shortcuts can be applied to solve in less moves. I wonder how many of those exist?
Right. This reminds me of Enigma not mapping a letter to itself. Perfect isn't quite the name for this, it's constrained with the outward appearance of being unpatterned and being very patterned having only 48 arrangements of a unique solution. When we see simple patterns, we think things are not truly random, hence fake random for Spotify playlists.
> There are 43,252,003,274,489,856,000 ways to arrange a Rubik’s cube. If I could evaluate a million arrangements per second, it would take over 1.3 million years to evaluate all arrangements. So, inspecting every individual arrangement is out.
For people who like powers of 2, that's "only" 2^65.2
That's within the realm of computability in practical timespans, if you can make the code fast and have $$$$$ to spend on compute. (modern CPU cores can do billions of operations per second, and that's not even considering GPUs)
The approach presented in the article is obviously far more efficient, but I wonder if anyone's done a "full search" of all possible cube positions before. I don't think there's any reason to do that, but that hasn't stopped people before (see: pi calculation records).
For me, any position which requires the full maximum 20 moves to solve would qualify as the perfect shuffle.
I wonder how many positions qualify (perhaps only 1 discounting symmetry as there is 1 fully solved cube, again discounting symmetry). But that’s a rabbit hole that I am not going down.
But I can appreciate the choice made in the article.
> perhaps only 1 discounting symmetry as there is 1 fully solved cube
I don’t see how ”there is 1 fully solved cube” would even hint at “perhaps only 1”
Also, there isn’t only 1. https://www.cube20.org/: “Distance-20 positions are both rare and plentiful; they are rarer than one in a billion positions, yet there are probably more than one hundred million such positions. We do not yet know exactly how many there are”
That page also shows their results for quarter turns, there are 3 (or fewer) with 26 quarter turns being the shortest they can be solved in. 36 (or fewer) needing 25 quarter-turns.
Except that the transform is relatively easy to reverse (compared to prime factorization) because of the properties of edge and corner pieces and limitations on piece movement that make a kind of spectral analysis possible. Things get a little better if you increase the size of the cube. Things get interesting if you allow un-solvable states (there's a 2:1 ratio of positions that are not naturally reachable) if you include in the protocol something like "always encode any corner rotations first" but it still wouldn't really be strong enough for modern compute.
If you mean to use it exclusively as a real-world key transmission like with Cryptonomicon's Solitaire decks, the problem becomes finding the shortest path or whatever the protocol determines is the normalized form.
Not to rain on your parade, it's a fun approach to think about, like maybe if the properties of a specific face determine which rotations to perform next, and which face to look at next, in addition to being the nonce for decoding the next letter. But even something like that would be too complicated to expect a person to remember all of while not being complicated enough to fluster a computational approach. The nice thing about Solitaire is that it's reasonable to perform the algorithm in your head.
IIRC they way they proved you can always solve a cube in 20 moves was essentially a bruteforce (after eliminating symmetries) so this the closest someone have done to full search.
The search was a little easier than that, as we knew how to solve every state in 20 moves, so the problem was proving some move that could be solved in 20 moves couldn't be done quicker in some unusual way. While that still took a while, the fact you knew the start and end limits how many moves you have to search.
This is an interesting insight. The OP's constraint that no two adjacent squares are the same color ensures non-randomness. (Which reminds us why people are so bad at producing "random" sequences.)
Yeah, it’s a funny coincidence that all those constraints to make it look random produces exactly one solution. I guess the OP knows this is not ‘random’ in the mathematical sense.
It actually looks somewhat regular instead of random in the end. Perhaps having only rule 6 and 3, no others, is interesting. Or 6, 3 and 1. Or only rule 3 and take solution with highest entropy
That’s a great reminder that what humans consider random and what is a truly random sets of states with high entropy are typically different things. In this case out of 43 quintillion combinations, there’s only 48 that fit the human imposed random criteria. In the case of passwords, websites typically ask for lots of additional constraints in what a password must have leading to dramatic reductions in the brute force effort required to find a password.
Par of why this is a strange goal is that two adjacent squares can be the same color, but not be in the correct relative position for an unscrambled cube. Rubik's cube is puzzle of cubelets, not squares
> There are 3 limitations:
> ...
> 2) I can place the first 11 edge pieces onto the cube any way I want. The orientation of the last edge piece is determined by the orientation of the first 11.
> 3) I need to track how many swaps I create by placing those pieces. An even number of swaps is solvable, and odd number is not.
Would it be equivalent to say, after placing the first 10 edge pieces, the position of the 11th is mandated, and then the orientation of the 12th is too? Or if (3) is broken might it be harder to fix than swapping the 11th and 12th?
Kind of.
But it introduces an artificial difference between edges and corners. You'd get the same ability for corners if you did them after the edges.
The slightly counterintuitive “magic” is that you can trade a corner swap for an edge swap: for permutation parity, corners and edges are interchangeable.
I loved reading this, but I can't help but think that a "perfect scramble" would be one that can ONLY be solved in 20 moves, i.e no shortcuts can be applied to solve in less moves. I wonder how many of those exist?
Right. This reminds me of Enigma not mapping a letter to itself. Perfect isn't quite the name for this, it's constrained with the outward appearance of being unpatterned and being very patterned having only 48 arrangements of a unique solution. When we see simple patterns, we think things are not truly random, hence fake random for Spotify playlists.
> There are 43,252,003,274,489,856,000 ways to arrange a Rubik’s cube. If I could evaluate a million arrangements per second, it would take over 1.3 million years to evaluate all arrangements. So, inspecting every individual arrangement is out.
For people who like powers of 2, that's "only" 2^65.2
That's within the realm of computability in practical timespans, if you can make the code fast and have $$$$$ to spend on compute. (modern CPU cores can do billions of operations per second, and that's not even considering GPUs)
The approach presented in the article is obviously far more efficient, but I wonder if anyone's done a "full search" of all possible cube positions before. I don't think there's any reason to do that, but that hasn't stopped people before (see: pi calculation records).
This was done in 2010 thanks to the analysis of the symmetries inherent in the underlying group theory, and about 35 CPU-years:
https://www.cube20.org/
For me, any position which requires the full maximum 20 moves to solve would qualify as the perfect shuffle.
I wonder how many positions qualify (perhaps only 1 discounting symmetry as there is 1 fully solved cube, again discounting symmetry). But that’s a rabbit hole that I am not going down.
But I can appreciate the choice made in the article.
> perhaps only 1 discounting symmetry as there is 1 fully solved cube
I don’t see how ”there is 1 fully solved cube” would even hint at “perhaps only 1”
Also, there isn’t only 1. https://www.cube20.org/: “Distance-20 positions are both rare and plentiful; they are rarer than one in a billion positions, yet there are probably more than one hundred million such positions. We do not yet know exactly how many there are”
There are about 490 million of them, the full list can be downloaded from that same cube20 site
https://www.cube20.org/distance20s
You can trim it down by counting in quarter moves.
That is, count a 180° move as two 90° moves. Which it is, though we usually don't think of it that way.
Assuming a random move length distribution, that would only leave a (2/3)^20 fraction of them, which is about 147000 positions.
That page also shows their results for quarter turns, there are 3 (or fewer) with 26 quarter turns being the shortest they can be solved in. 36 (or fewer) needing 25 quarter-turns.
https://www.cube20.org/qtm/
Seeing the "bits" that way makes me think there's a way to encode an ssh key into a rubix cube (a-la the "spy shuffle" decks).
Reminds me a bit of the "randomart" seeing the positions and colors of the cube splayed out like that.
Except that the transform is relatively easy to reverse (compared to prime factorization) because of the properties of edge and corner pieces and limitations on piece movement that make a kind of spectral analysis possible. Things get a little better if you increase the size of the cube. Things get interesting if you allow un-solvable states (there's a 2:1 ratio of positions that are not naturally reachable) if you include in the protocol something like "always encode any corner rotations first" but it still wouldn't really be strong enough for modern compute.
If you mean to use it exclusively as a real-world key transmission like with Cryptonomicon's Solitaire decks, the problem becomes finding the shortest path or whatever the protocol determines is the normalized form.
Not to rain on your parade, it's a fun approach to think about, like maybe if the properties of a specific face determine which rotations to perform next, and which face to look at next, in addition to being the nonce for decoding the next letter. But even something like that would be too complicated to expect a person to remember all of while not being complicated enough to fluster a computational approach. The nice thing about Solitaire is that it's reasonable to perform the algorithm in your head.
IIRC they way they proved you can always solve a cube in 20 moves was essentially a bruteforce (after eliminating symmetries) so this the closest someone have done to full search.
The search was a little easier than that, as we knew how to solve every state in 20 moves, so the problem was proving some move that could be solved in 20 moves couldn't be done quicker in some unusual way. While that still took a while, the fact you knew the start and end limits how many moves you have to search.
I want to flip coins so randomly that I never see the same face twice in a row.
This is an interesting insight. The OP's constraint that no two adjacent squares are the same color ensures non-randomness. (Which reminds us why people are so bad at producing "random" sequences.)
Yeah, it’s a funny coincidence that all those constraints to make it look random produces exactly one solution. I guess the OP knows this is not ‘random’ in the mathematical sense.
It actually looks somewhat regular instead of random in the end. Perhaps having only rule 6 and 3, no others, is interesting. Or 6, 3 and 1. Or only rule 3 and take solution with highest entropy
For all the Rubik's Cube enthusiasts here: here's a two-dimensional one in JavaScript - https://www.huehnken.de/games/circles/
Also a solution looking for a problem, maybe.
OP’s perfect scramble takes 18 moves to solve. Does that mean all Rubik’s Cube arrangements can be solved in 18 moves or less?
God's Number has been proven to be 20. It can't be any lower.
https://www.cube20.org/
Its quite a pretty arrangement IMO. There is a mix of randomness and regularity in it.
I'll keep my Rubik's Cube in this position.
That’s a great reminder that what humans consider random and what is a truly random sets of states with high entropy are typically different things. In this case out of 43 quintillion combinations, there’s only 48 that fit the human imposed random criteria. In the case of passwords, websites typically ask for lots of additional constraints in what a password must have leading to dramatic reductions in the brute force effort required to find a password.
Par of why this is a strange goal is that two adjacent squares can be the same color, but not be in the correct relative position for an unscrambled cube. Rubik's cube is puzzle of cubelets, not squares