God's number
Posted: Fri Nov 20, 2020 10:41 pm
https://en.wikipedia.org/wiki/God%27s_algorithm wrote:
<<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 moves, the idea being that only an omniscient being would know an optimal step from any given configuration. 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 designated "final configuration", a singular configuration, or one of a collection of configurations. To solve the puzzle a sequence of moves is applied, starting from some arbitrary initial configuration. A solution is optimal if the sequence of moves is as short as possible. This count is known as God's number, or, more formally, the minimax value. 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.......................................................................................................
Rubik's Cube: 43,252,003,274,489,856,000 "configurations"
(If one had one standard-sized Rubik's Cube for each "configuration",
one could cover the Earth's surface 275 times,
or stack them in a tower 261 light-years high.)
Rubik's Cube can be solved in 26 quarter turns moves or 20 full moves in the worst case. 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 proven 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. Mathematician David Singmaster had "rashly conjectured" this number to be 20 in 1980.......................................................................................................
The Fifteen puzzle: 10,461,394,944,000 "configurations"
The Fifteen puzzle can be solved in 80 single-tile moves or 43 multi-tile moves in the worst case. For its generalization the n-puzzle, the problem of finding an optimal solution is NP-hard. Therefore, whether a practical God's algorithm for this problem exists remains unknown, but appears unlikely.......................................................................................................
The Towers of Hanoi: 2n "configurations"
The Towers of Hanoi puzzle with the number of disks = n can be solved in a Mersenne number Mn = 2n − 1 moves.>>