On the generalization of the Tower of Hanoi graph

• Lia Martins UFAM / IFAM
• Jonas Costa UFAM
• Rosiane de Freitas UFAM

DOI: https://doi.org/10.5753/etc.2024.3006

Abstract

The classic Tower of Hanoi (ToH) puzzle consists of a base with three pegs P = p₀, p₁, p₂ and a set of n discs D = {d₁, d₂, ..., d_n} of different sizes, where d_i < d_j if i < j. In the initial state, all disks are stacked on p₀ in descending order of size, a perfect regular state. The objective of the game is to transfer all the discs to p₂, in this same arrangement, obeying the following rules: (1) only one disc can be moved at a time, and always the disc at the top of one of the pegs; (2) the disc d_i can only be placed on d_j if i < j. H_n is denoted as the ToH graph with n disks. H_n characterizes all possible regular states and the moves that can be made from one state to another. In this work, a recursive algorithm is presented which, starting from the base case H₁ and a cycle C₆, generates the ToH graph for any number of disks (H_n).

References

Poole, D. G. (1994). The towers and triangles of professor claus (or, pascal knows hanoi). Mathematics Magazine, 67(5):323–344.

Zhang, Z., Wu, S., Li, M., and Comellas, F. (2016). The number and degree distribution of spanning trees in the tower of hanoi graph. Theoretical Computer Science, 609:443–455.