The Mathematics of the Rubik’s Cube (2009) [pdf]
web.mit.edu
web.mit.edu
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....
It’s trivial to do 10k random rotations in memory. At which point you have something indistinguishable from random.
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.
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.
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.
Plus figuring out how to implement the various ways of checking validity was a lot of fun.
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.
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.
For example, in the picture below, the red square is at FUR, yellow at RUF, blue at URF, and green at ULBThe key take away is that all you need to do is find a few basic operations (swapping an edge/corner/center) that leaves the rest of the cube unchanged, and then your job is basically done, you apply these until you have a solved cube.
This might approach might not give you the optimal algorithm, which has been shown to be able to solve any Rubik's Cube in 20 turns or less [0].
You may have some more success in other areas of advanced math, particularly abstract algebra, graph theory, and related fields. You'll find more connections between that and what we do as developers than between programming and differential equations. And not just in the sorts of problems we solve (routing, etc.), but also in mapping between the structure of programs/architectures and concepts in algebra and graph theory.
Another crucial thing for me (post-college) is the absence of grading or immediate external or internal pressure. If I have trouble with a math or CS concept, I just set it down. It has no impact on remaining employed or future job prospects (well, mostly, some geometry and trig refreshers were good when doing some geographic stuffs; learning some languages were critical to a job, but that's not theory). Additionally, I removed the pressure from myself. If I don't get something, I don't (as I did in college, which led to other problems) see it as a personal defect or deficiency. It's just a fact, I simply don't understand it. I re-read the same material over and over across a several year period (Knuth's Concrete Mathematics) before certain sections of it became accessible to me. I desired to understand it, so I returned to it. But despite the desire, I didn't feel any external or internal pressure to understand it at that precise moment. When understanding came, it was a good feeling. But when it didn't, it was just a thing.
same with history. In school it was boring but now I listen to historical audiobooks all the time and love it.
Well, they are indeed difficult if you want to develop a new method of solving an equation or if you have discovered a new type of equation (which does not happen a lot these days). Otherwise, solving a differential equation seems to be not much more than simply a matter of recognizing a pattern and choosing the corresponding method.
> It is a BS opinion that one which says that maths is something got by putting bricks over bricks. By the contrary, it consists of an eternal returning to the same points, ever seeing them from a different perspective, with deeper understanding.
But want to point out the same concept within programming. As a programmer most of us learned to get things done, but often poorly, when we started. Instead of an array, your early programs likely used A1, A2, A3, etc. Then you learn arrays and suddenly what seemed like a bear to maintain was made trivial, and the utility of for loops was made obvious. Dozens, hundreds, maybe even thousands of lines of code could be eliminated with simple patterns from these early programs.
See things like The Evolution of a Haskell Programmer [0] for an entertaining take on this idea. When you start viewing mathematics in a similar light it can really help improve your level of math comprehension rapidly.
Sure, you could do sums before you learned calculus. But it was tedious to sum up N values of a discrete function (without a computer, of course). Then you learn calculus and find out how to integrate that function and then the summation becomes as trivial as the integration (easy in some cases, hard in others). Instead of treating each new math concept as totally new or a level above the thing before, examine how prior problems can be solved in light of this new concept. And, like programming, there will be a hundred ways to solve a particular problem (different data representations, different techniques). Learn to see the same problem from multiple perspectives and see how that shifts the difficulty of solving it.
[0] https://www.willamette.edu/~fruehr/haskell/evolution.html
https://www.ryanheise.com/cube/theory.html https://www.ryanheise.com/cube/fundamental_techniques.html
From there you should have enough of an understanding to start Googling things, playing with a cube, and Learning the Heise method: https://www.ryanheise.com/cube/heise_method.html
I've gained a lot more appreciation for group theory from exploring math of the Rubik's cube.
Second year was when we took the intro to abstract algebra course. One of the requirements my professor had was that we each had to do a term project involving material from the class. I couldn't think if anything interesting, so went to to see the professor to see if he had any suggestions for interesting project areas.
He simply said "The answer is in your hands". I looked at my hands, and realized I had been carrying my cube with me. Oops. I hadn't even figured out how to solve the stupid thing yet, let alone understand anything mathematical about it, and now my grade would depend on understanding it? DoH!
One of the first people at Caltech to figure out how to solve it was Peter Shor. Until there were a fair number of other people who had figured it out, Peter was nice enough to make a nightly circuit of the student houses solving people's cubes for them.
I remember one strange night when Peter came around right as several of us where wondering if some particular thing was reasonably do-able. The group wondering this also happened to be high on LSD at the time. (To be clear, Peter was not tripping. He just encountered the tripping group on his nightly cube solving circuit).
Both Peter and one of the tripping people started working on the problem. The strange thing was that the tripping person was not a theory guy. He was a strictly experimental cubist. But for some reason he was just staring at his cube thinking about the problem.
And Peter, who would usually figure out these things with theory instead was just furiously trying things.
Peter and the tripping guy both solved it at the same time, while the rest of us wondered if we had entered the Twilight Zone.