God's algorithm

God's algorithm is a notion originating in discussions of ways to solve the Rubik's Cube puzzle, coined by David Singmaster, but which can also be applied to other combinatorial puzzles and mathematical games. It refers to any algorithm which produces a solution having the fewest possible moves, the idea being that an omniscient being would know an optimal step from any given configuration.

The notion applies to puzzles that can assume a number of "configurations", with a relatively small, well-defined arsenal of "moves" that may be applicable to configurations and then lead to a new configuration. Solving the puzzle means to reach a designated "final configuration", a singular configuration, or one of a collection of configurations. To solve the puzzle a sequence of moves is applied, starting from some arbitrary initial configuration.

An algorithm can be considered to solve such a puzzle if it takes as input an arbitrary initial configuration and produces as output a sequence of moves leading to a final configuration (if the puzzle is solvable from that initial configuration, otherwise it signals the impossibility of a solution). A solution is optimal if the sequence of moves is as short as possible. This count is known as God's number. God's algorithm, then, for a given puzzle, is an algorithm that solves the puzzle and produces only optimal solutions.

Some writers, such as David Joyner, consider that for an algorithm to be properly referred to as "God's algorithm", it should also be practical, meaning that the algorithm does not require extraordinary amounts of memory or time. For example, using a giant lookup table indexed by initial configurations would allow solutions to be found very quickly, but would require an extraordinary amount of memory.

Instead of asking for a full solution, one can equivalently ask for a single move from an initial but not final configuration, where the move is the first of some optimal solution. An algorithm for the single-move version of the problem can be turned into an algorithm for the original problem by invoking it repeatedly while applying each move reported to the present configuration, until a final one is reached. Conversely, any algorithm for the original problem can be turned into an algorithm for the single-move version by truncating its output to its first move.

...
Wikipedia