It’s trivial to do 10k random rotations in memory. At which point you have something indistinguishable from random.
That’s easily corrected (e.g: flip a coin first to determine whether to do 10k or 10k+1 random rotations), but this shows it is easy to make slip ups solving such a seemingly trivial problem.
Rotating top side left one is the same as rotating bottom 2 sides right.
But, more generally limiting rotations to 90 degrees slows things down as 90 or 180 degree rotations can be directly computed with the same overhead.
My analogy is to Markov chain Monte Carlo. It is well known that MCMC on a discrete space will converge to the desired distribution (we’ll get to that in a second) if the chain is irreducible and aperiodic.
Irreducible means any state can eventually transition to any other state using the permutations allowed. This is easy to validate if we just use the various face rotations. Aperiodic essentially means that there is no fixed “loop” from one state back to itself that occurs with probability one. (The even parity issue that @someone raised comes in here. An absolute fix in the lack of full understanding of all possible such issues is to allow null moves with some low probability.). For a simple state space like this, the main thing is to make the permutations chosen in such a way that all states are reachable.
OK, iterated permutations converge in distribution, but to what? All the states in the target distribution here have equal probability, so (in MCMC terms) the posterior is totally flat:
P(s) / P(s’) = 1
What is reversible? It means that, if you are at state s, you are just as likely to go to s’ as if you are at s’ and going to s. [1] The easy way to ensure this is to make “clockwise twist of left face” chosen with the same probability as “counterclockwise twist of left face”.
This is the obvious strategy anyway, which is why reversible samplers are popular.
So in sum, the recommended algorithm is to start from any legal state and perform “N” permutations randomly chosen from clockwise/counterclockwise (50/50 chance) rotations of a randomly chosen face. To accomplish the null moves, just subtract a small random number from N.
On a discrete state space, you will get exponentially fast convergence to the desired distribution. The space is strongly connected, because you can get from any state to any other state with at most 40 moves.
I don’t see the problem here.
[1] https://en.m.wikipedia.org/wiki/Metropolis–Hastings_algorith..., A(x, x’) = 1.
The World Cube Association requires "equal probability for each state" by scramble programs used for their events.
You're right that a large number of rotations will result in something indistinguishable from random by an individual, but that is not sufficient according to WCA regulations as it's not uniformly random.
If I can hand you multiple sets of 10^10 cubes and you can’t tell which method was used that’s what I mean from indistinguishable not simply humans can’t tell.
Sum 20 coin flips mod 3 and you can find the bias in the output. It’s hard with a small sample set, but you could do it. Sum 10k coin flips and it’s a different situation.
Eventually you fall through the noise floor for any reasonable sample size.
Plus figuring out how to implement the various ways of checking validity was a lot of fun.
Secondly, I don’t see why would want to pick a ‘random’ position that way. If those numbers were correct, it would mean a 1:21 probability that your ‘random’ position was zero moves from the solution.
Edit: I think you simply didn't understand what I was talking about. The distribution of states is not even. If you randomly perform moves on a cube then you're more likely to end up in certain states.
As to the distribution of states, I am not sure what you mean. Insufficient shuffling can introduce bias, but that gets reduced as you continue shuffling. You can trivially shuffle past the point where remaining bias is not detectable. Unless, you want a specific bias, then that’s more easily achieved generating a random number with a specific format.
I created a 2x2 Rubik's cube in Java as my freshman final project for my second computer science class, but it was quite ugly.
Recently, I decided to take another look at implementing the cube - this time using Python. I also wanted a way to generate cubes and check if they were valid. The main representation of the cube is as a permutation group - a 48-tuple where each element in the tuple is unique. The solved cube is represented as (0, 1, ... , 46, 47).
Turns of the cube simply permute this tuple. To figure these all out I spent a lot of time with a cube covered in post it notes.
All of the stuff I implemented in the checking for valid cube comes from this stackoverflow post: https://math.stackexchange.com/questions/127577/how-to-tell-...
I've had a lot of fun working with this cube as my personal project. I recently created a Django website and a RESTful API to display randomly generated cubes. Soon I'll be working on a data pipeline to process these random cubes and display them nicely.
I've looked into working on a solution algorithm to implement Thistlethwaite's algorithm - https://www.jaapsch.net/puzzles/thistle.htm. I think this will take me a while, but it should be doable. I haven't really though too much about implementing it, but I think the way to do it is to define what it is for each step to be completed and then BFS a graph of moves to end up in that state. If anyone has looked into this I'd love some advice!
You can find the code I've written on Github: https://github.com/elliotmartin/RubikLite/blob/master/Rubik....