Hacker News Reader

Comment by Confusion | Hacker News Reader

jacquesm said:

  They explicitly state that they did not generate the
  optimal number of moves

You say:

  They state that they can solve random positions optimally

Those two statements contradict each other. However: AFAIK the existing algorithm, which they used, has not been proven to solve the problem optimally. It has now been shown that it can solve any position in at most 20 moves, but there's still the chance it solves a position in 20 moves that could optimally be solved in 19. Because the upper bound of 20 moves coincides with the proven lower bound of 20 moves, we know God's number. That does not mean that this must be God's algorithm.

View on HN

"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.

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.

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.

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.

Reply on news.ycombinator.com