Re:"God's Number" is 20 - Rubik's cube has been "solved"
by DougBTX on Monday August 09, 2010 @07:32AM
(#1587652)
"can" is conditional, so the two statements do not contradict. They can solve random positions optimally at 0.36 positions per second. But their goal was to lower the upper bound on God's number to 20, not to find all the optimal solutions. So what they did do, for all starting positions, was find good solutions, which they can solve at a rate of 3,900 positions per second.
[ Parent
| on HN ]
Re:"God's Number" is 20 - Rubik's cube has been "solved"
by Confusion on Monday August 09, 2010 @09:41AM
(#1587911)
True, they indeed do not contradict each other. I hadn't yet heard that there actually was an algorithm that could find optimal solutions, but I admit it's been a long time since I was interested in the issue.
Because of the time difference between generation a solution and generating the optimal solution, I'm guessing the algorithm bruteforces the optimal solutions, which explains part of the confusion: I was thinking about an algorithm that generates the optimal solution directly.
Re:"God's Number" is 20 - Rubik's cube has been "solved"
by tman on Monday August 09, 2010 @07:35PM
(#1589894)
I have the feeling you're not a programmer. An algorithm that generates the optimal solution for a given configuration is trivial. Do a breadth-first search of the results of each move until you get to a solved cube. Ta da, you're done!
Now, if you want to do it fast, that's a different story.
Re:"God's Number" is 20 - Rubik's cube has been "solved"
by Confusion on Tuesday August 10, 2010 @01:35AM
(#1590566)
An algorithm that could find the optimal solution in practice. For instance, in 0.36s, as in the article. A theoretical algorithm that finds the optimal solution is trivial; you don't need to be a programmer to come up with that one.