File FifteenPuzzle.h

↰ Parent directory (ADS/intractable)

The GIOCO DEL QUINDICI of section 19.5 (Samuel Loyd, 1878): n^2 - 1 tiles numbered 1 to n^2 - 1 on an n x n grid with a hole, a move slides a tile next to the hole into it, and the goal has the tiles in increasing order and the hole last.

Definition (ADS/intractable/FifteenPuzzle.h)

Detailed Description

solvePuzzle() is the branch-&-bound of the text: a node is a configuration, its children those one move away, its cost the number of moves from the root, its lower bound the sum of the distances of the tiles from their places [see manhattan()], and the next node visited the one of least cost plus bound, by a priority queue (the algorithm A* of Hart, Nilsson and Raphael with a consistent heuristic, so that the first goal extracted is optimal). A configuration is reached from the goal if and only if the parity of its permutation, plus that of the row of the hole when n is even, matches the goal [see solvable()]. The map of the least level of each configuration is a parameter of solvePuzzle(), std::map by default, so that the same search runs on the maps of std, Boost or Namespace ADS with the same nodes.

Beyond the text, two searches that work with any goal, e.g., the spiral one of puzzleSpiralGoal() (1 2 3 / 8 0 4 / 7 6 5 for n = 3): puzzleBFS() visits the configurations in breadth, so that the first goal reached is one of the fewest moves, with no heuristic and therefore many more nodes than A*; puzzleDFS() is the backtracking in depth that goes back when a configuration is already on the current path or the moves exceed a bound, and so finds a solution of at most that many moves, if any, not necessarily the shortest one.

The contracts [see File Contract.h]: a configuration is a permutation of [ 0 , n^2 ), and a solution returned goes from it to the goal by moves. The operations are defined in FifteenPuzzle.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 19.5, https://algoritmicamente.it/materiali/libro/capitoli/cap19.pdf

    1. Hart, N. J. Nilsson, B. Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions on Systems Science and Cybernetics 4(2), 100-107, 1968, doi:10.1109/TSSC.1968.300136

    1. Johnson, W. E. Story, Notes on the “15” puzzle, American Journal of Mathematics 2(4), 397-404, 1879, doi:10.2307/2369492

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions

Typedefs