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 stands for any practical algorithm that produces a solution having the least possible number of moves, the idea being that an omniscient being would know an optimal step from any given configuration.

[edit] 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 modelled 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 position, and else signals the impossibility. 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.

For the notion of "God's algorithm" to be meaningful, it must further be required that the algorithm be practical, meaning that it does not require extraordinary amounts of memory or time. Without this requirement, a "God's algorithm" always exists trivially. The simplest trivial algorithm is one that essentially contains a massive pre-computed table indexed by initial configurations, giving an optimal solution for each entry.

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 becomes an algorithm for the single-move version by truncating its output to a single move.

[edit] Examples

It is unknown whether a God's algorithm exists for Rubik's Cube.

Further information: Optimal solutions for Rubik's Cube

For the N-puzzle, a generalized 15-puzzle, the problem of finding a solution is known to be NP-hard. However, whether a God's algorithm for this problem exists remains unknown.^[1]

For the Towers of Hanoi puzzle, a God's algorithm exists for any given number of disks.^[2]

[edit] References

1. ^ 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.
2. ^ Carlos Rueda, "An optimal solution to the Towers of Hanoi Puzzle". [1]

• David Joyner, Adventures in Group Theory. Johns Hopkins University Press (2002). ISBN 0-8018-6947-1.

Rubik's Cube Edit

Inventor Ernő Rubik Normal Rubik's Cube 2×2×2 | 3×3×3 | 4×4×4 | 5×5×5 Cubic variation Square 1 | Skewb Non-cubic variation Megaminx | Pyraminx | Skewb Diamond | Dogic | Alexander's Star Derivative Rubik's Magic | Rubik's Clock | Rubik's Snake Notable player of Rubik's Cube Shotaro "Macky" Makisumi | Katsu | Jessica Fridrich | Tyson Mao |Bob Burton, Jr. | Lars Petrus | Edouard Chambon Solutions God's algorithm | Optimal solutions for Rubik's Cube Mathematics Rubik's Cube group