A Torre de Manaus e outros Jogos de Torres: propriedades em Grafos e Algoritmos

Abstract

In this research, the puzzle game Tower of Manaus (ToM) is proposed, which is a variation of the classic Tower of Hanoi (ToH) with capacity constraints on the pegs. Thus, given a structure with 3 pegs and n disks, the first peg supports all n disks, while the second and third pegs support at most n-1 and n-2 disks, respectively. The goal is, starting from an arbitrary initial configuration, moving all disks to the first peg, respecting both the capacity constraints and the ToH game rules, always moving one disk at a time and never placing a larger disk on top of a smaller one. Depending on the initial configuration, the goal may not be achievable, which results in a nonconnected graph. Thus, the characterization of the ToM graph is given, which models all possible configurations of the game as vertices, and the valid transitions between them as edges. Properties of this graph, such as the number of vertices and connected components, are explored. An algorithm to solve the game when possible is also proposed, presenting an algorithm to decide whether the goal is achievable from a given configuration or not. Additionally, a compilation of graph modeling and algorithmic aspects of the main variations of ToH found in the literature is presented. Among them, the Towers of London and Oxford, which were known only as neurocognitive tests, are formalized as combinatorial games. Finally, a formalization of the recursive construction of the ToH graph is proposed, using only elements of Graph Theory, which was not yet known in the literature.