God's algorithm
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 puzzle
s and mathematical game
s. 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.
s 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 puzzle
s 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 puzzle
s, 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.
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.
, a generalized 15-puzzle, the problem of finding an optimal solution is known to be NP-hard
. 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.
An algorithm for finding optimal solutions for Rubik's Cube was published in 1997 by Richard Korf. 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. Thus 20 is a sharp upper bound
on the length of optimal solutions. This number is known as God's number.
Rubik's Cube
Rubik's Cube is a 3-D mechanical puzzle invented in 1974 by Hungarian sculptor and professor of architecture Ernő Rubik.Originally called the "Magic Cube", the puzzle was licensed by Rubik to be sold by Ideal Toy Corp. in 1980 and won the German Game of the Year special award for Best Puzzle that...
puzzle, but which can also be applied to other combinatorial puzzle
Puzzle
A puzzle is a problem or enigma that tests the ingenuity of the solver. In a basic puzzle, one is intended to put together pieces in a logical way in order to come up with the desired solution...
s and mathematical game
Mathematical game
A mathematical game is a multiplayer game whose rules, strategies, and outcomes can be studied and explained by mathematics. Examples of such games are Tic-tac-toe and Dots and Boxes, to name a couple. On the surface, a game need not seem mathematical or complicated to still be a mathematical game...
s. 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 puzzlePuzzle
A puzzle is a problem or enigma that tests the ingenuity of the solver. In a basic puzzle, one is intended to put together pieces in a logical way in order to come up with the desired solution...
s 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 puzzle
Mechanical puzzle
A mechanical puzzle is a puzzle presented as a set of mechanically interlinked pieces.- History :The oldest known mechanical puzzle comes from Greece and appeared in the 3rd century BC....
s like Rubik's Cube
Rubik's Cube
Rubik's Cube is a 3-D mechanical puzzle invented in 1974 by Hungarian sculptor and professor of architecture Ernő Rubik.Originally called the "Magic Cube", the puzzle was licensed by Rubik to be sold by Ideal Toy Corp. in 1980 and won the German Game of the Year special award for Best Puzzle that...
, Towers of Hanoi, and the 15 puzzle. The one-person game of peg solitaire
Peg solitaire
Peg solitaire is a board game for one player involving movement of pegs on a board with holes. Some sets use marbles in a board with indentations. The game is known simply as Solitaire in the United Kingdom where the card games are called Patience...
is also covered, as well as many logic puzzle
Logic puzzle
A logic puzzle is a puzzle deriving from the mathematics field of deduction.-History:The logic puzzle was first produced by Charles Lutwidge Dodgson, who is better known under his pen name Lewis Carroll, the author of Alice's Adventures in Wonderland...
s, such as the missionaries and cannibals problem
Missionaries and cannibals problem
The missionaries and cannibals problem, and the closely related jealous husbands problem, are classic river-crossing problems. The missionaries and cannibals problem is a well-known toy problem in artificial intelligence, where it was used by Saul Amarel as an example of problem...
. These have in common that they can be modeled mathematically
Mathematical model
A mathematical model is a description of a system using mathematical concepts and language. The process of developing a mathematical model is termed mathematical modeling. Mathematical models are used not only in the natural sciences and engineering disciplines A mathematical model is a...
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.
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
Lookup table
In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than...
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.
Examples
For the n-puzzleN-puzzle
The 15-puzzle is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The puzzle also exists in other sizes, particularly the smaller 8-puzzle...
, a generalized 15-puzzle, the problem of finding an optimal solution is known to be NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
. 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.
An algorithm for finding optimal solutions for Rubik's Cube was published in 1997 by Richard Korf. 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. Thus 20 is a sharp upper bound
Upper bound
In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element of P which is greater than or equal to every element of S. The term lower bound is defined dually as an element of P which is lesser than or equal to every element of S...
on the length of optimal solutions. This number is known as God's number.
See also
- Oracle machineOracle machineIn complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
- Divine move
- Optimal solutions for Rubik's CubeOptimal solutions for Rubik's CubeThere are many algorithms to solve scrambled Rubik's Cubes. The maximum number of face turns needed to solve any instance of the Rubik's cube is 20. This number is also known as the diameter of the Cayley graph of the Rubik's cube group. An algorithm that solves a cube in the minimum number of...
- Proofs from THE BOOKProofs from THE BOOKProofs from THE BOOK is a book of mathematical proofs by Martin Aigner and Günter M. Ziegler. The book is dedicated to the mathematician Paul Erdős, who often referred to "The Book" in which God keeps the most elegant proof of each mathematical theorem...