God's algorithm

From Wikipedia, the free encyclopedia

God's algorithm is a notion originating in discussions of ways to solve the Rubik's Cube puzzle, 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 number of moves, the idea being that an omniscient being would know an optimal step from any given configuration.

Scope and definition

The notion applies to puzzles that can assume a finite 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 specific designated "final configuration" (or one of a collection of final configurations) by applying a sequence of moves, starting from some arbitrary initial configuration.

Some well-known puzzles fitting this description are mechanical puzzles like Rubik's Cube, Towers of Hanoi, and the 15 puzzle. 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 the arcs.

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. 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.[1]

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.

Examples

The Fifteen puzzle can be solved in 80 single-tile moves[2] or 43 multi-tile moves[3] in the worst case. For its generalization the n-puzzle, the problem of finding an optimal solution is known to be NP-hard.[4] Therefore, whether a practical God's algorithm for this problem exists remains unknown, but appears unlikely.

For the Towers of Hanoi puzzle, a God's algorithm exists for any given number of disks, however, the number of moves is exponential in the number of disks.[5]

An algorithm for finding optimal solutions for Rubik's Cube was published in 1997 by Richard Korf.[6] While it had been known since 1995 that 20 was a lower bound on the number of moves for the solution in the worst case, it was proved in 2010 through extensive computer calculations that no configuration requires more than 20 moves.[7] Thus 20 is a sharp upper bound on the length of optimal solutions. This number is known as God's number.[8]

See also

Notes

  1. ↑ Joyner, page 149
  2. ↑ A. Brüngger, A. Marzetta, K. Fukuda and J. Nievergelt, The parallel search bench ZRAM and its applications, Annals of Operations Research 90 (1999), pp. 45–63.
  3. ↑ "The Fifteen Puzzle can be solved in 43 moves". Domain of the Cube Forum
  4. ↑ Daniel Ratner, Manfred K. Warmuth (1986). "Finding a shortest solution for the N × N extension of the 15-puzzle is intractable". in Proceedings AAAI-86. National Conference on Artificial Intelligence, 1986. pp. 168–172.
  5. ↑ Carlos Rueda, "An optimal solution to the Towers of Hanoi Puzzle".
  6. ↑ Richard E. Korf, "Finding optimal solutions to Rubik's Cube using pattern databases", Proc. Nat. Conf. on Artificial Intelligence (AAAI-97), Providence, Rhode Island, Jul 1997, pp. 700–705.
  7. ↑ "God's Number is 20". Cube20.org
  8. ↑ Jonathan Fildes (August 11, 2010). "Rubik's Cube quest for speedy solution comes to an end". BBC News. 

References

  • David Joyner (2002). Adventures in Group Theory. Johns Hopkins University Press. ISBN 0-8018-6947-1. 
This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.