God's algorithm

[2] It refers to any algorithm which produces a solution having the fewest possible moves (i.e., the solver should not require any more than this number).

To solve the puzzle a sequence of moves is applied, starting from some arbitrary initial configuration.

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.

The one-person game of peg solitaire is also covered, as well as many logic puzzles, such as the missionaries and cannibals problem.

These have in common that they can be modeled mathematically as a directed graph, in which the configurations are the vertices, and the moves are the arcs.

For its generalization the n-puzzle, the problem of finding an optimal solution is NP-hard,[8] so it is not known whether there is a practical God's algorithm.

[9] An algorithm to determine the minimum number of moves to solve Rubik's Cube was published in 1997 by Richard Korf.

[4] Some well known games with a very limited set of simple well-defined rules and moves have nevertheless never had their God's algorithm for a winning strategy determined.

While chess computers have been built that are capable of beating even the best human players, they do not calculate the game all the way to the end.

[19] In 2007 Schaeffer et al. proved this to be so by calculating a database of all positions with ten or fewer pieces, providing a God's algorithm for all end games of draughts which was used to prove that all perfectly played games of draughts end in a draw.

[20] However, draughts with only 5×1020 positions[21] and even fewer, 3.9×1013, in the database,[22] is a much easier problem to solve –of the same order as Rubik's cube.