Solving 43,252,003,274,489,856,000 positions of Rubik's Cube

[Jouni]

I find this really stunning feat (sorry if already discussed here):

http://www.cube20.org/

Jouni

[bob]

I find this really stunning feat (sorry if already discussed here):

http://www.cube20.org/

Jouni

Not so stunning to me. Given their program, we could produce this answer in about 2 weeks using both of our clusters simultaneously. Computational power is quite remarkable today.

[Don]

I find this really stunning feat (sorry if already discussed here):

http://www.cube20.org/

Jouni

Jouni,

I did a bunch of work on Rubiks cube (with Keith Randal) when I worked for MIT. We built a solver that could solve a given position in about 1 hour. That was back in the early 90's on a quad Dec alpha which is considerably slower than todays machines.

I wrote the initial code and found a clever way to massively reduce the search time by getting early cutoffs using a data structure that had some things in common with a bloom filter.

Keith Randal added an additional bounds test - by noting that a 2x2 cube is a subset of the 3x3 if you look at the corners only. So if the 2x2 subset required 10 moves to solve, the 3x3 would take at least that many to solve. Being able to produce these reliable bounds made the problem solvable, even though it still required a lot of CPU power.

We used the quarter turn metric and searched hundreds of cubes including some we tried at random. We never found any cubes that took longer than 24 to solve. The web page you are looking at gives 20 as the longest cube or "God's number" but they are using the half turn metric. We know that in quarter turns it takes at least 24 for the most difficult cube.

You can generate random cubes that take an odd number of turns to solve just by starting with a solved cube and giving it an odd number of random twists, such as 101 twists for instance. So we generated a lot of "odd" cubes hoping to find a 25 cube but we never managed to find any cubes that could not be solved in 23 turns. But we could never prove it nor were we able to find "God's number."

So this is pretty interesting stuff to me. I'm happy to see that somebody did it.

[Andrew]

For anyone who hasn't seen it, the program available here
http://kociemba.org/cube.htm
can solve random cubes optimally and very fast.

These pages also have a lot more interesting cube information!

Andrew