God's Algorithm

[doubleyou]

Hello,

The other day my father showed me this article about a couple of cube entheusiasts/ math students (if I remember right) from the UK who has actually written a program that proves a method for solving the 3x3x3 in with an average move count of only 26 moves!
you heard right!! 26 moves!!

well, in the first attempts the program worked for over 63 hours to make out the solution. but imagine how it would feel to be able to look at the cube in that same perspective?

so its possible.

now, who would like to know this solution? XD

 

[aznfury]

I would like to know please.

 

[AvGalen]

http://www.ccs.neu.edu/home/gene/papers/rubik.pdf

http://kociemba.org/cube.htm

 

[Johannes91]

Optimal average is below 20 moves, actually.

 

[TimMc]

Optimal average is below 20 moves, actually.

Yeah, I thought the paper said that the maximum upper bound was 26 moves... lower 17 or something...

 

[AvGalen]

Optimal average is below 20 moves, actually.

The only way to "prove" that is to take a statistical analysis like this which leads to a very accurate approximation of 17.7 optimal moves on average and 97% is solvable in 18 moves or less.

It also discusses the 26 moves prove and how there is/was a gap in the theory.

Short summary:
Theoretical prove for every cube <= 26/27 (Never more than 26/27 moves)
Practical prove for every cube <= 20 (Sometimes 20 moves)
For a random cube: 26% = 17, 69% = 18 so 95% for 17 or 18 moves

P.S. I think the optimal number of moves for a cube of any size can be found with these formulas:
Uneven (n=1,3,5,etc): (n-1)*10
Even (n=2,4,6): ((n-1)*10)+1
Or a bit more "mathy" (n being a natural number): ((n - 1) * 10) + (n + 1) mod 2

For n=1 this means 0
For n=2 this means 11
For n=3 this means 20
For n=4 this means 31
For n=5 this means 40
For n=6 this means 51

I have no mathematical prove for this algorithm, but it is proven to be accurate for n=1 and n=2 and it looks to be accurate for n=3. It also takes into account the fixed/non-fixed centers difference and finally it fits the way both the number of "possible configurations" and the number of "possible turns resulting in configurations" grow. Once again, this is not hard prove, but I think it will turn out to be accurate.

 

[deKeijzer]

@ doubleyou, if you use cubeExplorer you can find that *near* optimal solution for every cube you input.

It`s like the rubiks.com cube solver, only it solves it in about 20 moves

 

[AvGalen]

It only takes cube Explorer a second to find a *near* optimal solution (21 or less). Finding (one of) the optimal solutions can take anywhere from 1 second to 1 hour on my laptop.

 

[doubleyou]

the articel presented it as it has just happened.
I have known optimal cube solvers for a long time. I guess this is not new after all then.

shame on me beginning to forget about fridrich and all :X

 

[AvGalen]

Optimal cube solvers can solve any cube in the least amount of moves possible and are pretty easy to program. It becomes more difficult if you want to get the result today, not somewhere this century.

The problem with optimal solving is that you never know how many moves it will take to solve the cube. That is what this article is about. It tries to prove that every cube can be solved in 26 moves or less.

It is easy to prove that 1 single cube can be solved in 18 moves, but what if there is 1 out of all those possible cubes that requires 25 moves?

 

[hdskull]

imagine how crazy it would be if someone actually memorize all of the scrambles, i think matyas can do it, haha jk

 

[AvGalen]

Just imagine this:

If every person on earth could optimally solve 1 cube per second it would take 200 years before all cubes are done.

Now replace person with pc and you 1 cube per second with about 5 minutes and this becomes:

If every person on earth had a brand new computer and would put it to work on this project it would take 60000 years to complete.

a) I don't think you would like to see the results of all this work in print
b) Why would we start now? If computers become twice as fast every 18 months (old "rule") we can be lazy and do nothing for 18 months, then start the project and be finished 30001.5 years from now.
Or wait another 18 months and be finished 15003 years from now. or...let's just wait a while and try to do it the smart-way for now, by using math+brains, not math+brute-force.

 

[doubleyou]

AvGalen, you are pretty good at these kinds of calculations
..
I like the fact that I can (same goes for all around here) solve the cube on the fly and the move count doest get much higher the double the OPTIMAL (which is pretty much, but acceptable compared to memorizing that many scrambles XD )

 

[AvGalen]

Seriously, double the optimal?
That means you solve in about 17.7*2 = 35/36 moves on average. You should definately start doing fewest moves!

For me a typical solve is about 70 moves (keyhole + 4 look last layer). Fridrich is about 55 moves and Petrus about 48. Which method do you use?