Re:"God's Number" is 20 - Rubik's cube has been "solved"
by jacquesm on Monday August 09, 2010 @07:11AM
(#1587615)
Ok, that sounds like a sensible summary of the positions.
If I understand you correctly a god algorithm is allowed to produce the required result using whatever strategy, including partial brute forcing/searching, backtracking in order to arrive at its solution as long as it does so in a reasonable time, so is not 'brute force' per se.
The reason why that didn't sit right with me (I accept your wikipedia quote as what construes a god algorithm) is that for me the 'god' algorithm would imply there is no better one, since with omniscience you don't need to make any false moves and I could not imagine a true god algorithm would be allowed to make false moves.
But I guess I was wrong there.
Thanks for digging that up!
Re:"God's Number" is 20 - Rubik's cube has been "solved"
by sesqu on Monday August 09, 2010 @03:33PM
(#1589081)
So you're looking for an algorithm that produces the optimal result heuristically, without making any false moves, instead of using the convenient lookup table that God has available to him? Sounds very NP to me.
According to Wikipedia a God Algorithm only has to be 'practical', find the optimal solution to a position with a sensible amount of processing. So it can use search and back-tracking. We could term your algorithm that works without search and back-tracking as a God God Algorithm because it is an optimal sequence of processor moves that find the optimal sequence of cube moves. A God God Algorithm would be awesome, but a much more difficult thing to create. I imagine it would run orders of magnitude faster than their God Algorithm.
(PS. I don't think we can entirely rule out the possibility that the God God Algorithm might contain some small amount of search or back-tracking.)