Exponential vs. Subexponential Tower of Hanoi Variants

Abstract

We deal here with Tower of Hanoi variants played on digraphs. A major source for such variants is achieved by adding pegs and/or restricting direct moves between certain pairs of pegs. It is natural to represent a variant of this kind by a directed graph whose vertices are the pegs, and an arc from one vertex to another indicates that it is allowed to move a disk from the former peg to the latter, provided that the usual rules are not violated. We denote the number of pegs by $h$. For example, the variant with no restrictions on moves is represented by the Complete graph K$_h$; the variant in which the pegs constitute a cycle and moves are allowed only in one direction is represented by the uni-directional graph Cyclic$_h$. For all 3-peg variants, the number of moves grows exponentially fast with $n$. However, for $h \ge 4$ pegs, this is not the case. For example, for Cyclic$_h$ the number of moves is exponential for any $h$, while for a path on $4$ vertices it is $O(\sqrt{n}3^{\sqrt{2n}})$. This paper characterizes the graphs for which the transfer of a tower of size $n$ of disks from a peg to another requires exponentially many moves as a function of $n$. To this end we introduce the notion of a shed, as a graph property. A vertex $v$ in a strongly-connected directed graph $G=(V,E)$ is a {\it shed} if the subgraph of $G$ induced by $V(G)-\{v\}$ contains a strongly connected subgraph on $3$ or more vertices. Graphs with sheds will be shown to be much more efficient than those without sheds, for the particular domain of the Tower of Hanoi puzzle. Specifically, we show how, given a shed, we can indeed move a tower of disks from any peg to any other within $O(\lambda^{n^{\alpha}})$ moves, where $\lambda > 1$ and $\alpha = \frac{1}{2} + o(1)$. For graphs without a shed, this is impossible.