God's algorithm

God's Algorithm (English God's Algorithm ) is a term from discussions on the optimal solution to the Rubik's Cube . The formulation comes from the English group theorist John Conway or one of his colleagues in Cambridge. It can also be related to other problems in combinatorics and game theory . It describes any algorithm that always produces a solution with the smallest possible number of steps or moves.

Scope and definition

The term refers to puzzles that can take on a finite number of "configurations", with a rather small, well-defined set of "trains" representing transformations between configurations. Solving a puzzle means reaching one or more specific specific “end configurations” (of a finite number) from any arbitrary starting configuration by using a sequence of moves. Such a train sequence corresponds to a solution to the puzzle.

Some well-known puzzles match the description, e.g. B. Mechanical puzzles like the Rubik's Cube, Towers of Hanoi and the 15 puzzle . Also Solitaire is one of them, as many logic puzzle how the problem of missionaries and cannibals . What they have in common is that they can be mathematically modeled as a directed graph , whereby the configurations correspond to the nodes ("points") and the trains to the edges ("arrows") of the graph. A solving train sequence (a solution to the puzzle) corresponds to a (directed) path in the graph, which leads from an initial to an end configuration.

An algorithm is called solving if it has an arbitrary initial configuration as input

outputs a solution if the puzzle is solvable from the initial configuration, and otherwise
reports that there is no solution.

A solution is called optimal if the sequence of moves is as short as possible, and a solving algorithm for a puzzle is called God's algorithm if it always gives an optimal solution. Finally, God's number is defined as the length of the longest train sequence among all optimal solutions.

A real “God's algorithm” should also be practicable ; H. do not require excessive storage space or time. In the case of many puzzles, it would be possible to quickly find a solution with the help of a huge lookup table indexed over all start configurations, but this procedure would require too much memory.

Instead of asking for a complete solution, you can also ask for the best first single move after the start configuration. An algorithm for individual trains can be transformed into an algorithm for the overall solution by repeating it until the final configuration. Conversely, the algorithm for the overall solution can also be broken down into algorithms for individual trains.

Examples

problem	God's number	Size of the state space	Merit / Notes	year
N-Puzzle (the general 15-Puzzle )	?	?	NP-complete , compare Ratner and Warmuth	1990
15 puzzle	80 (average 52.6)	${\ displaystyle {\ frac {16!} {2}} = 10,461,394,944,000}$	Korf and Schultze	2005
8 puzzle	31 (average 22)	${\ displaystyle {\ frac {9!} {2}} = 181.440}$	Reinefeld	1993
3 puzzle	6 (average 3)	${\ displaystyle {\ frac {4!} {2}} = 12}$	Reinefeld	1993
Towers of Hanoi with n panes	${\ displaystyle 2 ^ {n} -1}$	${\ displaystyle 3 ^ {n}}$	see also Rueda	historical
Rubik's Cube	20 (quarter and half turns) 26 (quarter turn only; half turn counts as 2 quarter turns)	${\ displaystyle {\ frac {8! \ cdot 3 ^ {8} \ cdot 12! \ cdot 2 ^ {12}} {3 \ cdot 2 \ cdot 2}} =}$ ${\ displaystyle 43.252.003.274.489.856.000}$	Rokicki, Davidson, Dethridge and Kociemba, see also Optimal Solutions of the Rubik's Cube	2010 2014
chess	?	?	An endgame database in chess finds the shortest path to checkmate .

literature

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

Individual evidence

↑ See Jerry Slocum: The Cube. The Ultimate Guide to the World's Bestselling Puzzle. Secrets - Stories - Solutions. New York: Black Dog & Leventhal, 2009, p. 26.
↑ D. Ratner, M. Warmuth: Finding a shortest solution for the (NXN) extension of the 15-puzzle is intractable . Journal of Symbolic Computation 10 (1990), pp. 111-137
^ Richard E. Korf; Peter Schultze: Large-Scale Parallel Breadth-First Search (PDF; 104 kB). In: AAAI Conference On Artificial Intelligence. Proceedings of the 20th national conference on Artificial Intelligence 3 (2005), pp. 1380-1385, here pp. 1384-1385 (Fifteen Puzzle), Table 2 (States as a Function of Depth for Fifteen Puzzle).
↑ ^a ^b Alexander Reinefeld: Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA *. In: Proceedings of the 13th International Joint Conference on Artificial Intelligence (1993), Chambery Savoi, France, pp. 248-253.
↑ Carlos Rueda: "An optimal solution to the Towers of Hanoi Puzzle" ( MS Word ; 33 kB)
↑ God's Number is 20

[1] See Jerry Slocum: The Cube. The Ultimate Guide to the World's Bestselling Puzzle. Secrets - Stories - Solutions. New York: Black Dog & Leventhal, 2009, p. 26.

[2] D. Ratner, M. Warmuth: Finding a shortest solution for the (NXN) extension of the 15-puzzle is intractable . Journal of Symbolic Computation 10 (1990), pp. 111-137

[3] Richard E. Korf; Peter Schultze: Large-Scale Parallel Breadth-First Search (PDF; 104 kB). In: AAAI Conference On Artificial Intelligence. Proceedings of the 20th national conference on Artificial Intelligence 3 (2005), pp. 1380-1385, here pp. 1384-1385 (Fifteen Puzzle), Table 2 (States as a Function of Depth for Fifteen Puzzle).

[Reinefeld_1993-4] Alexander Reinefeld: Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA *. In: Proceedings of the 13th International Joint Conference on Artificial Intelligence (1993), Chambery Savoi, France, pp. 248-253.

[5] Carlos Rueda: "An optimal solution to the Towers of Hanoi Puzzle" ( MS Word ; 33 kB)

[6] God's Number is 20

God's algorithm

contents

Scope and definition

Examples

See also

literature

Individual evidence