The Origin of Algorithms?

[Jilvin]

Okay, I was trying to memorise some more PLL when a thought crossed my mind.

Who originally came up with these algorithms? If that's too obvious, then HOW did they come up with them?

Did they just sit there with a cube and happen to come across them or was there some mathematics involved?

Any answers would be nice, thank you!

 

[Theromy]

It'll be some mathematical equation. Not sure who invented them, did Jessica Fridich invent the PLLs and OLLs since they are used in her method? Or did she make a method using PLLs and OLLs :s

My guess is that it would be some mathematician

 

[ExoCorsair]

I would guess that it was initially done by breaking the previous step, fixing something, restoring the step that was broken.

 

[AlexandertheGreat]

I remember when I first started speedcubing I came across an old book from a library that some mathematician had made discussing the mathematical aspects of the cube. If I recall correctly, there was another mathematician named Thistletwaithe who, in the 80's came up with a master algorithm for solving the cube. So I think that's the origin of algorithms. Also, this guy named Singmaster invented the notation for moves that is generally used, called Singmaster notation.
As for Fridrich algorithms, I'm pretty sure Jessica Fridrich used a modified version of the F2L that other cubers already used. The last layer algorithms were I think of her own creation, and I think she would just play around with the cube until she figured OLLs and PLLs out.

 

[AvGalen]

Most PLL's were found by hand without the use of any math. If you play around with the cube and remove/move/re-insert F2L pairs you can find a lot of PLL's and OLL's yourself.

There are also computerprograms (Acube, Cube Explorer) that can find optimal algorithms or algorithms with only certain face-moves (RU for example)

Most of the currently used algorithms are either 2-Gens or variations of optimal algs that require more moves but are more fingertrick friendly

And people still find better/faster algorithms.

 

[joey]

I don't understand how you could use math to find algorithms. I have never come across a branch of maths that could relate to finding algorithms.

EDIT:

UMM, group theory stuff? Yeh, I'm a bit of an idiot. I was tired, when I wrote that.

 

[badmephisto]

I don't understand how you could use math to find algorithms. I have never come across a branch of maths that could relate to finding algorithms.

yes its possible, of course... by use of commutators etc. But noone does it this way. It's almost trivial to write a computer program that finds solutions to PLLs only using given set of moves, like R U F or something, ... optimal and other as well. You can then have it print all the solutions, go through them, and rule out those that don't have easy finger tricks.

I made a very simple C program some time ago that did this for me, and I programmed it to prefer moves such as R U R' U' because they are very easy triggers, but my computer is too crappy to search moves that need more than 12-13 or so twists... which is not too high, so that's a problem.

 

[AvGalen]

I could think of two ways to use math to find algorithms:

1) For computer programs. Go to http://kociemba.org/cube.htm and read everything under "The Mathematics behind Cube Explorer" (left-side, bottom)
2) Every face you turn on the cube changes orientation of some pieces. By figuring out the orientation of all pieces of a PLL. Math could be helpfull for this approach (I think)

However, a simple U-PLL like (M D M') U (M D' M') U (M D M') U2 (M D' M') only requires some imagination and intuition. No math or computers

 

[Marcell]

Jessice herself writes on her site: "Most of the algorithms were developed by myself during the time period between the summer 1981 and the spring of 1983."
Many OLLs and PLLs can be quite easily found. However, these algs are often not too good for speedcubing, that's why most people use different algs then the original ones on Jessica's site.

 

[Johannes91]

I don't understand how you could use math to find algorithms. I have never come across a branch of maths that could relate to finding algorithms.

yes its possible, of course... by use of commutators etc. But noone does it this way.

Did you ask everyone, or how do you know? Some people like solving problems on they own, although that's not common among speedcubers.

I made a very simple C program some time ago that did this for me, and I programmed it to prefer moves such as R U R' U' because they are very easy triggers, but my computer is too crappy to search moves that need more than 12-13 or so twists... which is not too high, so that's a problem.

Blaming your computer is ridiculous. Write better programs.

 

[badmephisto]

I made a very simple C program some time ago that did this for me, and I programmed it to prefer moves such as R U R' U' because they are very easy triggers, but my computer is too crappy to search moves that need more than 12-13 or so twists... which is not too high, so that's a problem.

Blaming your computer is ridiculous. Write better programs.

You missed the point: It doesn't matter that my program is flawed, which by the way, I am completely aware of. I was merely expressing my belief that computer algorithms are an excellent way to find solutions to PLL's/OLL's, given of course that someone takes the time and effort to design a program that does this efficiently. And while I don't deny that many of the algorithms were surely figured out by-hand, manually, this certainly looks like a type of problem that is perfectly suitable for a computer, and I wouldn't be surprised to learn that majority of the PLL's/OLL's I use were in fact just output of one such program.

 

[Radu]

imo everyone can discover new algorithms.... just take a solved cube and do a few moves, cycles, simetrical moves etc ..you'll get some twisted corners, moved edges etc. so...the moves you did had a result that you can memorize and use in the future

maybe i have a different vision of the cube than the others..but i think that every set of moves can be considered an algorithm...i hope i'll have in the future also some personal algs...but first i have to highly improve and learn a lot

 

[Johannes91]

I was merely expressing my belief that computer algorithms are an excellent way to find solutions to PLL's/OLL's

Computers can find solutions very quickly, and not just for OLL and PLL but for the whole cube as well. But yet there are people who enjoy solving for fewest moves.

 

[csfield]

David Singmaster came up with mathematical algorithms. Group theory is the branch of mathematics involved. It's mainly based on commutators.

http://www.amazon.com/Handbook-Cubi...860016?ie=UTF8&s=books&qid=1191477283&sr=1-10

http://www.amazon.com/Notes-Rubiks-...6860016?ie=UTF8&s=books&qid=1191477283&sr=1-1

 

[Jason]

I was merely expressing my belief that computer algorithms are an excellent way to find solutions to PLL's/OLL's

Computers can find solutions very quickly, and not just for OLL and PLL but for the whole cube as well. But yet there are people who enjoy solving for fewest moves.

That's in fact wrong. For the moment no computer program has found the optimal solution for solving the cube, and mathematicians don't even know what th minimum amount of moves to solve the cube is. They only know it's between 20 and 26 moves (for the most mangled cube, obviously) To show a cube could necessarily be solved 26 moves or less took a few months using a cluster of supercomputers.

 

[Johannes91]

Computers can find solutions very quickly, and not just for OLL and PLL but for the whole cube as well.

That's in fact wrong. For the moment no computer program has found the optimal solution for solving the cube, and mathematicians don't even know what the minimum amount of moves to solve the cube is.

Obviously there's no single "optimal solution for solving the cube" because positions are different. But I wasn't talking about proving what the upper bound is, just about solving individual positions (and, actually, didn't use the word "optimally").

 

[Jason]

forreal, I suppose I got a bit carried away, sorry.
One thing I was wondering tho, is it possible to solve the cube in any way, writing down the solution as you go, then try to work out a more optimum solution using group theory from the written solution. Seeing that you're in one state when you start and there is one final state, surely different routes to getting to the solution aren't exclusive of each other.

 

[robertpauljr]

Okay, I was trying to memorise some more PLL when a thought crossed my mind.

Who originally came up with these algorithms? If that's too obvious, then HOW did they come up with them?

Did they just sit there with a cube and happen to come across them or was there some mathematics involved?

Any answers would be nice, thank you!

To get back to the original question:

Singmaster Interview

Read this interview, then get the books csfield gave links to if you haven't done so yet.