And Group Theory is Good Stuff, though I still haven't quite understand Lie Groups ("continuous groups of transformations (generally linear ones)")
This week, 14-year-old Lucas Etter set a new world record for solving the classic Rubik’s cube in Clarksville, Maryland, in the US, solving the scrambled cube in an astonishing 4.904 seconds. The maximum number of face turns needed to solve the classic Rubik’s cube, one that is segmented into squares laid out 3x3 on each face …
Lie groups are essentially just the same thing as all n x n invertible matrices, i.e., GL_n(k), where k is any field. If the field has a nice topology, say R or C, then you pull this topology back through the determinant map to get a topology on GL_n. All other Lie groups more or less look like this, in that they form a closed subgroup (i.e., inverse image of a closed subset of the reals under the determinant map) of GL_n(R) or GL_n(C). (This can be taken as a definition of a Lie group, but shouldn't if you are doing things properly. Which we aren't, since this is a comment thread on a news website.)
Something like this: a group is a collection of symmetries of an object. Any object will do, as long as it has constituent parts that possess symmetry. An example of a group is the group of Rubik's cube: the symmetries here are all moves, which might not look like symmetries because we swap the colours around, but if we ignore the colours then they are symmetries, and the colours are simply there to show you that you are doing a symmetry. Solving Rubik's cube is equivalent to the following: given a symmetry of Rubik's cube, write it as a sequence of "easy" symmetries, i.e., quarter turns of the slices.
This is an example of a finite group, where there are finitely many symmetries. Of course, there are objects with infinitely many symmetries, such as a disk. This has a rotation of any angle, and a reflection through any line passing through the centre. Another example of an infinite group is the real numbers, with addition being the way of combining objects. Here there is also a notion of closeness, in that two numbers are 'close' if their difference is 'small'. Of course, close and small are relative terms, and the appropriate mathematical concept to encapsulate this is a topology. A topology on a set, such as the real numbers, is a collection of subsets of it, called 'open sets', and they have to satisfy three basic properties: the empty set, the set with nothing in it, is open; the intersection of two open sets, so everything in both of them, is also open; the union of any number of open sets, so everything that's in any of them, is open.
For the real numbers, the open sets are collections of open intervals (a,b), which means all numbers between a and b, but not a and b themselves. Two numbers are 'close' if they are in lots of open sets together, in some sense.
If we have pairs of real numbers then we can put a topology on this, the 'product topology', which says that a set is open if it is the product of open sets in each variable, and then throwing in more open sets for this to be a topology. (Notice that, given any set of open sets, this can be a topology by including unions and intersections, so we can do this.)
There was no reason to choose just pairs of real numbers, we could have chosen n^2 real numbers: then we can arrange these numbers as n by n arrays, and this gives us a topology on all matrices. The determinant map is 'continuous', meaning that if we take an open subset of the real numbers, U, then all matrices with determinant in U form an open subset of the set of matrices.
With this topology, we can talk about matrices being close to one another, more or less their co-ordinates are close in the real numbers. If X is a group of invertible matrices, then it is closed if all other matrices form an open set, and closed groups of matrices are Lie groups.
That's some more words, but it might not be any better.
I did that, but I didn't think it would be very believable if I completed the whole thing so I only switched around one face.
Of course, the downside of this was I made it impossible to solve the cube after that. Wasn't until my cubemaster cousin tried and failed for some time that anybody realised my deceit...
I went one better: I typed up my own version of how to solve the cube, got my uncle to photocopy off a load of them, then would sit in the nearby shopping centre and wait for someone to come along and watch me solve it.
They'd say "I wish I could do that" or some such, at which point I'd flog them a copy of my solution for a quid (this was back in the days when a pound was actually real money, rather than small change!)
Made a tidy sum (which I'd then blow on video games in the local arcade, but that's another story!)
real money as in a little green note? Ahh the days when a 5p mixture paid was paid by a shilling coin or maybe 2 shilling coin and 10 half pennies in change....
Later on in life I worked in a call center at Christmas breaks. Rubiks cubes were great to while away the hours, we too had a "cheat sheet" for doing cubes (it was fairly long winded but worked every time). cant remember it now, might get one at Christmas and teach the kids.
My dad and I did the same, selling our A4 solution sheet for a quid. I also offered a cube-solving service at the school fête for 50p, I could deal with one customer per minute (without referring to the sheet). Some customers came back 3 or 4 times during the fête because they kept messing their cubes up again... they should have coughed up the extra for a sheet.
"I prefer Gordian Knot theory. Gives a far simpler solution"
Ah, the branch cut. Not a very complex solution.
(A Polish mathematician was on a flight when the pilot fell ill, and nobody else could fly. The crew asked him if he knew how to fly the aircraft: he said "alas no, I am but a simple Pole on a complex plane.")
That's pretty amazing. I thought a banjo player's fingers on a fret board were quick. I wonder how long it would take to arrange the each side of the cube in every possible combination, one after the other, using only the human hand and mind. Don't desert me boffins!
I wonder how long it would take to arrange the each side of the cube in every possible combination, one after the other, using only the human hand and mind.
Well, that's easier than arranging a cube in every possible combination simultaneously.
Let's assume Etter can in general iterate overy 27 configurations in 5 seconds. That's the starting configuration, plus 26 quarter-turn moves at worst to reach the solved configuration. Etter presumably uses half-turns as well as quarter-turns, but half-turns pass momentarily through their intermediate quarter-turn configuration, so we can assume quarter-turns with no loss of generality.
We can assume those 27 configurations are distinct, because if he reached the same configuration twice then he has a loop and he's not using an optimal path.
There are roughly 4.3e19 configurations. (4.3e19 / 27) * 5 gives us ~ 8.0e18 seconds to complete, or somewhere around a quarter of a million million years, plus some time for pee breaks.
If anyone's curious, a little back-of-the-envelope shows a Rubic's Cube has about 65 bits of entropy, assuming all configurations are equally probable. (They are, mechanically, but since RCs are sold in solved form, and many people manage to solve them and then leave them that way, at any given time the solved configuration probably appears disproportionately often across the entire state of extant RCs. So don't use the solved configuration as your Rubic's Passcube.)
In competition you get 15 seconds to inspect the cube before starting the solve. That is not long enough to plan the whole solve. Therefore an important part of solving is being able to quickly recognise which algorithm you are going to need next, after the one you are doing.
Recognition and look-ahead are what makes the difference between a quick solver and a fast solver.
Ouch, my lack of clarity bites again.
Quick = under 30 seconds
Fast = under 15 seconds
Very Fast = under 12 seconds
Contender = under 10 seconds
Amazing = under 8 seconds
The best cubers I have seen average 6 to 8 seconds. That's over 5 solves, discarding the fastest and slowest solve, averaging the middle 3.
World records usually happen when an Amazing solver gets a skip on the last layer (the last layer just happens to be solved by luck when the first two layers are solved).
That's why competitions use the average rather than a single solve.
...it takes a certain view of the world to do this.
I never solved a Rubik cube, but then neither did I ever pick one up to try.
And had I done so would have run out of patience after about three turns.
But then I do have the attention span of goldfish.
I do know people who would persevere with one of these infernal devices. None of them have much conversation, though.
I still use the same algorithm I used in 1983, and have had many cubes that have become destroyed by constant solving. I sometimes use a completed cube to make nice patterns and leave it on my desk for people to see (wow, how did he do that / smug git), or just therapy when talking to my IT department. I'm usually 2 - 4 minutes in slow mode, but then 'the real McCoy' official cube is not very good for speed cubing as it is actually quite stiff. Inferior models / copies actually tend to break!
I used to be able to do it in under 30 seconds (I remember using silicone grease to lube the thing to make it rotate easir - ha!), but again that was 35 odd years ago too, and I have forgotten how.
One think I always wondered about though - if you mix the cube in say, 10 turns, then surely the fastest solve is 10 turns?
"One think I always wondered about though - if you mix the cube in say, 10 turns, then surely the fastest solve is 10 turns?"
Definitely not. All it shows is that there is a way to solve it in ten turns. Suppose that you scramble it five times and unscramble five times, for example. You have a solved cube at the end, so the solution is 0 turns.
To see another reason why such thinking has to be wrong, mix the cube for, instead of ten turns, a million. It is never going to need a million turns to solve it then.
"I used to be able to solve the cube in about a minute. Forgotten how to now - it was 35 years ago."
Not quite as long on both counts: closer to 32 years ago, give or take, and I had it down to about 40 seconds.
The last time I picked one up, several years ago, I could only solve it some of the time. And much, much more slowly!
"Isn't it a bit like a race "to the nearest pub?" Depends very much on where you start."
TBH it depends on what shit the nearest pub serves. Reminds me of the film "the worlds end" and the pub crawl they do from one pub to the next cookie cutter pub. I even think the bandits were the same....
When I finally got round to buying a Rubik's Cube it came with a 'cheat sheet' which explained the sequence of twists required to move pieces around. I did eventually solve a jumbled cube but had no desire to memorise the algorithms nor perfect executing them at speed.
Despite having such little interest in Rubik's Cubes I do however enjoy wasting my time untangling topological puzzles. Each to their own I guess.
43,252,003,274,489,856,000 possible combinations. Add game theory to that, RPG with a dash of FPS for good measure.
You have 9 x 6 rooms to create, and where the player goes defines the setup of the next room. Equate player moves to rotations, jumble the initial settings at start, and you've got a really infinite game (for practical values of infinite, of course).
Doing a cube fast is an impressive feat of dexterity and memory. But it's only dexterity and memory. Is it really that big a deal that a fourteen-year-old can do it in five seconds? I wonder if he actually solved the cube himself, as opposed to finding out how it was done on the internet?
The vast majority of people I know who can do the cube have not actually solved it - they were just taught. In my day, it was via a photocopied crib sheet or a book; nowadays, it's on the internet.
I solved the cube - I actually solved it, from scratch, without recourse to help of any kind - back in 1981. It took me about three months. And yes, I found it useful to dismantle the cube and rebuild it. The algorithms I worked out are not efficient - but because I worked them out myself, they are well and truly stuck in my mind. I can still pick up a cube and do it. Normally takes me about five minutes.
So, I wonder how many people world-wide have actually solved the cube, rather than just learned how to do it from some other source? I wouldn't be surprised if it's a few thousand at most.
Until I read this I assumed everyone who'd solved it did so without help - how naive I was!
An IBM colleague in Nottingham, who'd discovered the Rubik's cube some time before they were on general sale in the UK, was selling them to interested colleagues including me. It also took me about three months to solve it the first time but I didn't dismantle it or move stickers. The second time took a few days, and after that I could do it in around 15 minutes. Then I got bored and haven't touched for the last 35 years or so, although I still have it somewhere.
For a time I was fascinated by the mathematics and realised there was a connection with group theory, although I wasn't clever enough to gain any interesting insights from this. I also wrote some code (on my 1kB Nascom 1 computer) to attempt to find useful sequences of moves - the tools described in the article.
Maybe it's time to get the cube out again and see if I can still do it.
The Git solved it and (almost) immediately lost interest in it. Only repeated it to demonstrate that I had solved it. Always thought there was something strange about the pursuit of speed: lubricating the damned thing with vaseline etc.
Mind you, my then new girlfriend and latterly ex-fianceé thought there was something strange about me waking in the middle of the night to test new strategies with the cube. Took around 2-3 months IIRC.
A friend showed my a way to solve it with two repeated moves.
You have to solved one face first quite easy, then do the opposite four corners with a move that swaps two corners and rotates a third.
Once all the bottom corners are solved, it's easy to solve the faces using another move which cycles three edge pieces only.
I could do it in a couple of minutes usually.
Probably more than a few thousand. But a lot less than the number of people who have learnt a solution from someone else. I solved the cube from scratch in three days, while at school. I forget whether it was a geography or a history lesson during which I for the first time got the cube back to its initial state. My first algorithm for solving the cube took about an hour to perform, and I needed a sheet of densely written notes in front of me. I later learnt to solve the cube in under a minute, but the tricks for doing that I mostly acquired from other people and I was never the class champion in the speed trials that took place in almost every breaktime back then...
@Martin, I had more or less the same experience. First I crafted a wooden model after just having seen an assembled Rubik's Cube. It did the job, but you could not turn it fast enough. So I bought the real thing and found a procedure which worked for 50% of the cases. On failure I just scrambled the cube at random and tried again. Eventually I lend my Rubik's Cube to a friend who was recovering from a brain injury. May be it is still in use in the hospital.
Back in 1981 I was actually in competition with my father to solve the cube, and he beat me by 2 weeks, and even then once he figured it out he refused to show me, I love my father, but sometimes he is a real pain! (yes he is still alive at 91)
So I figured I would get even with him, when they came out with a 4x4 cube I got a couple of them and we re-started the competition, and he beat me again! Ugggg! But I did solve the 4x4 eventually, it took my father about 4 months to figure it out, and it took me 6 months.
Two years ago my adult daughter got me a 7x7 cube for Christmas and I have yet to figure it out. It is devilishly hard, or maybe my brain is getting worn out, but I refuse to give up. Getting old sucks, but I guess it beats the alternative!
You could always tell someone that cheated by swapping the stickers as they quickly became loose and fell off. Also if you know how to solve it then it's easy to work out near the end if pieces have been swapped around incorrectly.
I learned to complete it from an A4 set of instructions someone sold me back in the day and I still have them somewhere and practice a few times every year or two to keep the muscle memory working.
I can remember a conversation back when they first came out with a neighbour who in a bit of one-up-manship was convinced she'd completed 5 sides...
Although, as mentioned, it is proved that you can solve a cube in a maximum of 20 moves, it takes a modern desktop computer more than 4.904 seconds to do the calculation (though in cube solving the timing only starts when you make your first move - you're allowed to look and ponder it first).
As I understand it, speed-solvers use a subset of more memorable moves which more typically take about 40 moves in practice - and these methods are far easier and more effective than the books/methods published in the early 1980's e.g. by Patrick Bossert or the math prof's booket from that era.
There is no known algorithm for solving Rubik's cube in the shortest possible number of moves, or even close to it. The proof was existence only, not constructive. One reason is that, for space requirements, they had to throw away any actual representations of the moves that they did find, and another is that the type of coset enumeration that I think they used isn't really well suited to storing this stuff.
"I've seen some fast Lego Mindstorms constructions "solving" the cube. Are they cheating by having a desktop plugged in rather than using the programming blocks?"
"I don't know how it counts officially, but a few years ago I did download a very nice Java applet which, given a few 10's of seconds, would calculate a sequence of 20 moves or less to solve any cube position. Probably this site: http://kociemba.org/cube.htm"
Ah, those aren't algorithms. Those are algorithms to find an algorithm, one level higher. An algorithm to solve in 20 seconds would be a series of instructions that took a cube and gave you the moves immediately. What these sorts of programs are doing is computing an optimal set of moves given a fixed state. You give it a different state, it has to do it all over again.
"Ah, those aren't algorithms. Those are algorithms to find an algorithm, one level higher. An algorithm to solve in 20 seconds would be a series of instructions that took a cube and gave you the moves immediately. What these sorts of programs are doing is computing an optimal set of moves given a fixed state. You give it a different state, it has to do it all over again."
Isn't this a case of "6 of one, half a dozen of the other"? The point is, you input the cube's current state and it outputs the way to solve it in in 20 moves or less (which if you want to get technical can then be applied to a mechanical cube turner to perform the feat). Shouldn't matter HOW it gets there, as long as it gets there (sorta like you get the same result whether you use a selection sort, a binary tree sort, or a quick sort).
PS. I once had a Rubik solver (albeit crude) for my Commodore 128 computer.
"Isn't this a case of "6 of one, half a dozen of the other"?"
Well, not really. Firstly, the algorithm does not guarantee to produce the right answer. Secondly there is a very easy algorithm to solve the cube in the shortest possible time: perform all sequences of one move, then reverse them, then all sequences of two moves, then reverse them, and so on. Eventually you will hit the fastest path to do it, although it might take millions of years to do so.
Would you call that an algorithm? It takes more than 20 moves because there's a lot of computation to work it out before you do it. It's obviously much slower than a reasonable human algorithm.
"Isn't this a case of "6 of one, half a dozen of the other"? The point is, you input the cube's current state and it outputs the way to solve it in in 20 moves or less (which if you want to get technical can then be applied to a mechanical cube turner to perform the feat). Shouldn't matter HOW it gets there, as long as it gets there (sorta like you get the same result whether you use a selection sort, a binary tree sort, or a quick sort)."
I know I've already replied to this, but I thought of a better example, one appropriate for IT. You phone up a helpdesk with a problem with your computer. Two things could happen:
1) They tell you what to do to solve it.
2) They tell you to just put your symptoms into Google, and after a few hours of frustrated searching you find a solution to the problem.
In both cases the helpdesk solved the problem, but the second isn't quite what we have in mind when we say 'helpdesk'. Or maybe it is...
Point is, either way, you end up with a solved cube, a fixed computer, or in an earlier example, a sorted list. May not be the optimal solution, but unless utmost efficiency is critical, many times you can get away with "good enough". Selection sort may not be the fastest sort around, but it has its uses when space is tight because it can sort in situ.
There are a lot of problems in which is it intractable to have an optimal solution, but sub-optimal solutions are very tractable. A good example of this is the Travelling Salesman Problem - which is known to be NP-Complete. However, if one accepts that we can accept a solution which is less than or equal to twice the optimal solution, this problem becomes tractable.
Although there may be an algorithm that will solve the cube in 20 moves, the one which solves it in 40 may be quicker from a computational point of view.
when people take part in competitive tests, does everyone start from the same starting point?
Or are they given random starting configurations of variable complexity?
It seems to me to be difficult to have a real competition without either having either (1) a known starting point for all or - which may favour some who "know" that configuration, or (2) have unequal starting points
"It seems to me to be difficult to have a real competition without either having either (1) a known starting point for all or - which may favour some who "know" that configuration"
As the article said, there are 43,252,003,274,489,856,000 configurations. Some are more amenable to certain algorithms than others, but they won't have much experience with the starting position, with better odds than me claiming you won't win the jackpot on the lottery twice in a row.
I remember at school in 1980 aged 13, there were two kids in my year who in a couple of days had independently worked out their own algorithms for solving the cube. I was in utter awe at their ingenuity and skill, particularly when they repeatedly clocked up solution times of under a minute using an official Rubik's cube that had been disassembled and all hinges greased for optimal speed. It's very liberating to realise your own averageness at an early age: I've been happily underachieving ever since :-)
I was leafing through a Rubiks Cube solution book at a bookstore a year or so ago and realized (or reaffirmed), in spite of my degree in "Computer Science", I'm not a mathematician. My brain is really, really not wired that way. I never did figure out the cube in the 1980's, and probably won't even if I live until the 2080's. Too boring to me. But building or optimizing a cube's guts so it turns faster? That would be way more interesting than solving the cube itself. To me, anyhows.
My best was 43 seconds, fastest in my school. There were only a couple of other guys who could solve it, and it took them well over 10 minutes.
I used to have everyone coming to me at break times to solve their cubes for them. I was doing dozens of cubes a day. At one point I developed RSI and a swollen index finger. My doctor and my mum banned me from the cube for a while.
I can still solve it, but takes me probably about 2-3 minutes now.
Kudos to these speed freaks.
You don't need a screwdriver. Just place the pad of your thumb over the middle piece and pull up. Then you can simply snap it back into place. By doing this carefully, no-one will see you do it. Practice this move until you can do it quickly and out-of-sight.
Now wait for the time some nitwit hands you their cube and challenges you to scramble it and time the solution. Do so, but as your last move pry out one cube and invert it. Turn back to the owner as you give the cube a couple more twists (for obfuscation and misdirection).
Hey presto! Unsolvable cube puzzle.
With a random scrambling of the cube, some solves are easier than others, so it is chance if you get an easier solve that takes less time.
Back when the cube was new I got one and got a booklet that showed various "tools" (using the article's terms) you could use toward solving it - yeah I should have figured them out on my own, but I was an impatient teenager! When I got good at it I could sometimes solve in under 20 seconds, but usually 30 was my average. The fast solves were just lucky in that I needed fewer tools to unscramble it.
Obviously to beat 5 seconds you not only need many more tools than I was using, but to execute them faster as well. But it will still remain up to luck how many tools you need (or tools with fewer individual moves required than other tools) If he got a different cube it might have taken him a couple seconds longer, if someone else who is as skilled as he is (if there is anyone, maybe he's really the best but the record isn't 100% proof of that) got that same pattern they would have got a similar time and owned the record instead of him.
The 15 seconds of inspection probably helps determine where to initially attack, but I found that I rarely had to stop and look at the cube during the solve. It is like anything where as you become good at it your vision becomes "faster" so you can instantly recognize the next pattern you want to attack and go from one tool sequence to the next. Perhaps with the more complex tools he would be using the inspection is more beneficial. What I was using were very simple sequences of 3-5 moves to do one thing, like flip an edge or rotate three edges, twist or rotate three corners, and so forth. He may be fixing all 8 corners in a single tool to start - inspection would really help there.
Cube envy? I already said my fastest times (when I got lucky with the initial setup) were almost 4x slower than him so I'm not claiming I was ever remotely in the same class (and I couldn't solve it at all now without re-learning everything, since I haven't touched one since)
All I'm saying is that there are probably others today who are as good or even better than him, who simply didn't get as lucky with the initial conditions in a timed run as he did. That matters. A lot.
I never had the patience to solve a Rubik's cube, but there was a boy in my wee sister's class at school who was world champion. He even took a gap year and went around the world, paying for it by entering speed-cubing competitions. The thing that I never thought to ask was how he knew he'd finished, as he was almost completely colour-blind.
In the final days of my high school career seeing a kid that had read a book about Rubiks Cube solving one behind his back. It took him about a minute I guess, and when he was done even he was impressed. Me, the only way I've ever "solved" a Rubik's Cube was to peel the stickers off it, and stick them back on. The cheap knock offs had stickers on them. Damned maddening puzzle from my perspective.
If you want to learn the basic beginner method for solving the 3x3x3, I have several tutorial sites, all free.. my latest one is www.fixmycube.com and you can also see my 160+ rubik vidoes at www.youtube.com/user/mountainscooter .. I make all the vidoes and animations myself and I do it for free, cause I want to see more people in the world solve the cube!
Biting the hand that feeds IT © 1998–2019