Optimal solution for Rubik's cube

[Solve]

I don't quite know where to put this post, because it is an overlap of the puzzle theory forum and the software forum. I was wondering how much computer power it would take to make an optimal solution for the Rubik's cube. Basically, God's algorithm.

If a computer scanned a Rubik's cube, it should be able to solve it in 20 moves or less. What type of software would this computer have? Would it have to be a supercomputer? How much time would it take this computer to find an optimal solution? An hour? A minute?

I really have no idea what the answer is to any of these questions, so I am excited to see what some people's answers are.

 

[wasianrubiks]

Well what about the android phone that solved it? Unless it was upgraded than it shouldn't even closesly resemble a computer's power?

 

[Ked Ki]

Actually, there's a fairly well-known computer algorithm that does find optimal solutions. It's called Kociemba's Algorithm, and it's actually not that much of a power hog. In fact, you could download the Optimal Cube Solver program from the Cube Explorer site, and run it on your computer.

Link: http://kociemba.org/cube.htm

 

[cuBerBruce]

The algorithm used for finding optimal solutions is called IDA*. Kociemba's 2-phase algorithm finds close to optimal solutions quite fast but does not guarantee optimality. Cube Explorer implements both algorithms, so with that program you can choose between fast solutions or guaranteed optimal solutions.

While Kociemba's 2-phase algorithm can generally find a 20-move solution quite quickly, I note that cube positions that actually require 20 moves are so rare that you hardly ever actually encounter them with random scrambles. Almost always, a 20-move solution is not optimal.

 

[riverchen]

Waiit, didn't OP say he wanted God's alg? Is that not the alg which solves every position?

 

[applemobile]

Gods alg being fewest move solution, devils alg being the one of which yoom be referring

 

[Stefan]

Is that not the alg which solves every position?

In the fewest possible number of moves, yes. The way you ask makes me think you're confused about "algorithm". "God's algorithm" isn't a fixed sequence of moves (what cubers sadly call algorithm) but an algorithm in the broader sense (a procedure, in this case one for finding cube move sequences).

 

[Solve]

So far I've heard about IDA* and Kociemba, but what about Thistlethwaite's algorithm? Or is that inferior to the other two?

 

[Stefan]

Thistlethwaite doesn't even belong in this thread (as it doesn't even attempt to find optimal solutions).

I recommend reading these if you haven't already:
http://www.jaapsch.net/puzzles/compcube.htm
http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube
http://cube20.org/ (particularly the history table)

 

[Solve]

Well, the reason I mentioned Thistlethwaite is because I saw it on that wikipedia entry, but I guess I should done some more research on it before mentioning it.

 

[Stefan]

Well, the reason I mentioned Thistlethwaite is because I saw it on that wikipedia entry,

As an early entry in the "Upper bounds" section, yes. But from there it was still a long way to optimality.

It's still decent if one is more interested in a simple implementation and low time/memory usage than in optimality of the solutions, as shown by the results of Tom's cube contest a while back:
http://tomas.rokicki.com/cubecontest/winners.html

 

[Solve]

Okay, so it was an attempt at fewest moves, but it was far from optimal. I liked an article that I found here:

http://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf

It had some good information.