I've been fascinated by the Rubik's cube for years after learning to solve one in 7th grade. I started to get back into it high school and dropped my solve times down below a minute. Then I continued in college and got down to 25 seconds average with a personal best of 15.15.
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.
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!
My only suggestion is trying to quickly validate a cube is solvable seems like a waste of time vs generating them via a large number of random rotations. Especially when no cube can be more than 20 rotations from a solution.
Checking whether a cube is valid is effectively a random-state generator; i.e. it randomly chooses one of the 43 quintillion possible states. Generating random moves biases towards certain scrambles. This is why the World Cube Association generates random states of the cube with their library TNoodle, rather than random sequences of moves.
Depends on what you call a ‘rotation’. After 10k random 90 degree turns of a face, you have an even permutation on both corners and edges, which means you can’t reach half the positions.
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.
You have been down voted, but I think this is a reasonable point and a reasonable question. It seems to me that the method of iterated transformation you suggest will indeed yield a random draw.
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
for all states s, s’. This means that a reversible Metropolis-Hastings sampler that just accepts every proposed move will converge to a flat posterior. OK, so we just need to make the permutations we propose reversible.
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.
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.
That’s not supporting your point, a solution that’s harder to mess up is suggested. Secondly, they specifically don’t want a truely ranodm sequence as they require a minimum number of moves from a solution.
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.
Except that simply isn't true. When randomly performing rotations you're much more likely to end up in certain states (as I mentioned in my other comment). Whether you make 10k random rotations or 20 random rotations you're still more likely to end up in a certain state.
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.
It's almost certainly less effort (though arguably also less fun) to write a valid state checker than it is to prove that N random cube operations will yield something that's within some tolerance of a uniform distribution across all legal cube states.
Some positions are far, far more common than others. So generating a cube by a random string of rotations biases towards these positions. Take a look at the count of positions table in the bottom right corner of this page: http://www.cube20.org/
Plus figuring out how to implement the various ways of checking validity was a lot of fun.
Firstly, that table doesn’t show the number of essentially different positions. For example, at distance 2, you have (54, by my count) positions where two faces were turned that do not share an edge and positions where they do.
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.
I don't think generating every possibility of a cube is reasonably doable - it's over 43 quintillion - 10^16
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.
For scale, fastest supercomputer is over 1.8 x 10^17 operations a second. So generating 10^16 numbers is not that bad for a distributed project over a few weeks.
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.
Is there a properly colorized version of this PDF floating around somewhere? In particular, I'm wondering about this line that lies above a grayscale image:
For example, in the picture below, the red square is at FUR, yellow at RUF, blue at URF, and green at ULB
The 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].
I really wish I had the brains to do math to figure out things like the Rubik's cube. I find it fascinating how you can model something like this and express it with math.
This 15 minute video is a pretty accessible explanation of a technique for solving Rubik's-type puzzles: A simple trick to design your own solutions for Rubik's cubes [1]
Not sure if you're referring to cube theory or just the ability to solve... If it's the former, almost anyone can learn to solve a Rubik's cube in a few days (albeit in a non-optimal fashion). It's a matter of learning a handful of algorithms for each layer then executing. It can quite a fun way to keep the hands busy while thinking, like crocheting or knitting.
I am talking about cube theory. Solving it isn’t that hard unless you want to be super efficient. But formalizing it in way you can then reason about seems very hard to me.
I remember after a few weeks I figured out a move that could swap two pieces without other changes or something like that (don't remember the details). It was horribly inefficient but it did the job.
To understand higher maths intelligence is not enough. It is necessary, but not sufficient. To understand mathematics, someone needs discipline and hard work. Years of preparation, years of study of topics you don’t know for what they can be useful. But, as far as you go deeper in maths, more you understand the meaning of the first steps and theirs contents. 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. Try to read again a book you had difficulties when in basic school. You will find it easy.
> 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.
I just remember that when we had three dimensional differential equations I kind of hit a wall. Until then I had a pretty good intuitive understanding of things but this requires a lot of work. Other people had no problems with this. On the other hand I don’t have to work much on understanding computers and software architecture so it seems this is a better area for me.
Differential Equations is often called Difficult Equations for a reason.
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.
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.
Fair. I have no anticipation of being at the cutting edge in math either. One thing that I have found, though, is that as I've explored (particularly in programming and CS) more areas, that reviewing the math I had trouble with in college it all seemed "easy", or at least easier. An advantage of age/experience is the ability to draw from our numerous experiences and produce better (for us, personally) analogies with the material.
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 here. I really wish I could go back to school and relearn some stuff I ignored back then. Back then I had to learn a lot of stuff just because but now I understand how they can be useful.
same with history. In school it was boring but now I listen to historical audiobooks all the time and love it.
I was a second year undergraduate math major at Caltech when the Rubik's Cube came out in the United States, and they quickly seemed to be all over campus.
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.
My group theory textbook mentioned the cube briefly, but no mention ever from the professor on it. It really would have helped me in the class because I had a hard time seeing how groups actually apply and why they're so useful.
I've gained a lot more appreciation for group theory from exploring math of the Rubik's cube.
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....