Comment by Retr0id
4 days ago
> 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”
3 replies →
There are about 490 million of them, the full list can be downloaded from that same cube20 site
https://www.cube20.org/distance20s
2 replies →
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.