[HN Gopher] The Rubik's Cube Perfect Scramble (2024)
___________________________________________________________________
The Rubik's Cube Perfect Scramble (2024)
Author : notagoodidea
Score : 79 points
Date : 2025-08-02 14:31 UTC (8 hours ago)
(HTM) web link (www.solutionslookingforproblems.com)
(TXT) w3m dump (www.solutionslookingforproblems.com)
| Retr0id wrote:
| > 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).
| HappyPanacea wrote:
| 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.
| CJefferson wrote:
| 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.
| ramses0 wrote:
| 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.
| kevindamm wrote:
| 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.
| kevindamm wrote:
| 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/
| stoneman24 wrote:
| 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.
| Someone wrote:
| > 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"_
| kevindamm wrote:
| There are about 490 million of them, the full list can be
| downloaded from that same cube20 site
|
| https://www.cube20.org/distance20s
| BurningFrog wrote:
| You can trim it down by counting in quarter moves.
|
| That is, count a 180deg move as two 90deg 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.
| kevindamm wrote:
| 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/
| Aardwolf wrote:
| 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
| superjan wrote:
| I want to flip coins so randomly that I never see the same face
| twice in a row.
| fastaguy88 wrote:
| 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.)
| superjan wrote:
| 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.
| lutzh wrote:
| 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.
| lupire wrote:
| 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
| liampulles wrote:
| 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.
| divbzero wrote:
| 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?
| venusenvy47 wrote:
| God's Number has been proven to be 20. It can't be any lower.
|
| https://www.cube20.org/
| rawling wrote:
| > 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?
| tripa wrote:
| 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.
| pama wrote:
| 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.
| davidpfarrell wrote:
| 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?
___________________________________________________________________
(page generated 2025-08-02 23:01 UTC)