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
Retr0id · 2h 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).
kevindamm · 1h ago
This was done in 2010 thanks to the analysis of the symmetries inherent in the underlying group theory, and about 35 CPU-years:
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.
ramses0 · 1h ago
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 · 1h ago
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.
HappyPanacea · 2h ago
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 · 1h ago
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.
No comments yet
lupire · 50m ago
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
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).
https://www.cube20.org/
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.
Reminds me a bit of the "randomart" seeing the positions and colors of the cube splayed out like that.
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.
Also a solution looking for a problem, maybe.
No comments yet