Battle of algorithms and numbers: God vs. Devil
No, I won't talk about philosophical-psychological creatures. Even math lovers won't get their money's worth due to my poor knowledge of group theory. This article aims to clarify the following terms: God's and Devil's algorithm; God's and Devil's number.
The God's algorithm, in terms of combinatorial puzzles, refers to such a move sequence that is equally long as in the case that a scrambled puzzle would be solved by God. Suppose God is omnipotent and omniscient. Therefore, God always knows the smallest number of moves which need to be applied to a scrambled cube (let's say 3x3x3 Rubik's cube) in order to be solved. This number of moves in God's algorithm is called the God's number (and for the Rubik's cube it equals 20 – in other words, the 3x3x3 cube is always solvable in 20 or less moves, regardless of initial scramble. If quarter turn metric is used (which means e.g. B2 is counted as two moves), the God's number for the 3x3x3 Rubik's cube is 26).
While the God's number is known for some puzzles, for others it still remains a mystery to find it. Usually it is not a simple mathematical task. Supercomputers and sophisticated analytical as well as numerical methods are needed for searching of all the possible puzzle states and solving them by means of the fewest moves.
In contrast to the God's algorithm, there is the Devil's algorithm. Unfortunately, it is not well defined. However, it is not a move sequence that would solve a scrambled puzzle in the "longest possible way" (in analogy to the God's number which is solving a scrambled position optimally in terms of number of moves). Some authors call the Devil's algorithm as such a sequence that reaches all the puzzle states. As an optimal Devil's algorithm is sometimes denoted a sequence of moves that reaches all the puzzle states exactly once.
Therefore, it is possible to say that if the Devil's algorithm was executed by a blind man, the puzzle would be solved at one point. Similarly to the God's algorithm, finding of the Devil's algorithm is not a trivial matter.
Sometimes a term Devil's number is also mentioned in terms of combinatorial puzzles. Just as in the case of the God's number, the Devil's number refers to the smallest number of moves in the Devil's algorithm. Unlike religion, it doesn't necessarily have to be number 666, 616 or another one widely used in connection with the Devil's number (number of the beast).
Recommended literature for persons concerned (links valid as of February 20, 2013):
http://anttila.ca/michael/devilsalgorithm
http://www.jaapsch.net/puzzles/hamilton.htm
http://www.cube20.org
http://en.wikipedia.org/wiki/God%27s_algorithm
http://www.jaapsch.net/puzzles/groups.htm
keywords for google: God's algorithm; Devil's algorithm; God's number; Devil's number