# Shortest paths in the Tower of Hanoi graph and finite automata

@article{Romik2006ShortestPI, title={Shortest paths in the Tower of Hanoi graph and finite automata}, author={Dan Romik}, journal={SIAM J. Discret. Math.}, year={2006}, volume={20}, pages={610-622} }

We present efficient algorithms for constructing a shortest path between two configurations in the Tower of Hanoi graph and for computing the length of the shortest path. The key element is a finite-state machine which decides, after examining on the average only a small number of the largest discs (asymptotically, $\frac{63}{38} \approx 1.66$), whether the largest disc will be moved once or twice. This solves a problem raised by Andreas Hinz and results in a better understanding of how the… Expand

#### Figures and Topics from this paper

#### 71 Citations

An efficient algorithm to determine all shortest paths in Sierpiński graphs

- Computer Science, Mathematics
- Discret. Appl. Math.
- 2014

An essentially optimal algorithm is constructed thus extending Romik's approach for p = 3 to the general case and employing a Markov chain argument it is shown that the number of input pairs needed for the decision is bounded above by a number independent of n. Expand

Algorithms and Bounds for Tower of Hanoi Problems on Graphs

- Computer Science
- 2008

This thesis studies a generalization of the classic Tower of Hanoi puzzle, considering graphs which are composed of ` SCCs, each one isomorphic to K3, and concentrate on the logarithm of time(H), looking for asymptotic vii. Expand

The Number of Moves of the Largest Disc in Shortest Paths on Hanoi Graphs

- Mathematics, Computer Science
- Electron. J. Comb.
- 2014

Numerical results, obtained by an algorithm based on a modified breadth-first search making use of symmetries of the graphs, lead to a couple of conjectures about some cases not covered by the ascertained results that may shed some light on the notoriously open FSC. Expand

Distances and automatic sequences in distinguished variants of Hanoi graphs

- Mathematics
- 2016

In this thesis three open problems concerning Hanoi-type graphs are addressed. I prove a
theorem to determine all shortest paths between two arbitrary vertices s and t in the General Sierpinski… Expand

Metric properties of the Tower of Hanoi graphs and Stern's diatomic sequence

- Computer Science, Mathematics
- Eur. J. Comb.
- 2005

A formula is given that counts, for a given vertex v, the number of vertices u such that there are two shortest u, v-paths in the Tower of Hanoi graphs, and implies that only for vertices of degree two this number is zero. Expand

On The Average-Case Complexity of the Bottleneck Tower of Hanoi Problem

- Mathematics, Computer Science
- ANALCO
- 2014

This paper settles the conjecture of Dinitz and Solomon from SOFSEM'07 in the affirmative, and shows that the average- case complexity of the BTH problem is asymptotically the same as the worst-case complexity, for all n and k. Expand

Shortest paths in Sierpiński graphs

- Computer Science, Mathematics
- Discret. Appl. Math.
- 2014

The set S u is completely determine, where u is any almost-extreme vertex of S k n, and the number of shortest paths between any fixed pair of vertices of SK n can be computed in O ( n ) . Expand

Twin Towers of Hanoi

- Computer Science, Mathematics
- Eur. J. Comb.
- 2012

A group, called Hanoi Towers group, of rooted ternary tree automorphisms, is used, which models the original problem in such a way that the configurations on n disks are the vertices at level n of the tree and the action of the generators of the group represents the three possible moves between the three pegs. Expand

Independent sets on the Towers of Hanoi graphs

- Mathematics, Computer Science
- Ars Math. Contemp.
- 2017

The number of independent sets is equivalent to the partition function of the hard-core lattice gas model with nearest-neighbor exclusion and unit activity in the Tower of Hanoi graph H n at stage n, and recursion relations for the numbers are derived. Expand

Extrema property of the k-ranking of directed paths and cycles

- Mathematics, Computer Science
- AKCE Int. J. Graphs Comb.
- 2016

This work finds the largest possible directed graph that can be obtained from a directed path or a directed cycle by attaching new edges to the vertices such that the new graphs have the same rank number as the original graphs. Expand

#### References

SHOWING 1-10 OF 18 REFERENCES

Metric properties of the Tower of Hanoi graphs and Stern's diatomic sequence

- Computer Science, Mathematics
- Eur. J. Comb.
- 2005

A formula is given that counts, for a given vertex v, the number of vertices u such that there are two shortest u, v-paths in the Tower of Hanoi graphs, and implies that only for vertices of degree two this number is zero. Expand

An analysis of the generalized Towers of Hanoi problem

- Computer Science, Mathematics
- BIT
- 1983

The shortest-path tree clearly characterizes the generalized Towers of Hanoi problem; and its use leads to a very simple analysis of the generalized problem. Expand

Shortest paths between regular states of the Tower of Hanoi

- Mathematics, Computer Science
- Inf. Sci.
- 1992

Two generalizations of the classical Tower of Hanoi problem 0, i.e., to transfer n discs from one peg to another by a series of legal moves, are considered and some mathematical background is developed to construct simple algorithms that solve problems 1 and 2 correctly and return the minimum number of moves. Expand

Graphs S(n, k) and a Variant of the Tower of Hanoi Problem

- Mathematics
- 1997

For any n ≥ 1 and any k ≥ 1, a graph S(n, k) is introduced. Vertices of S(n, k) are n-tuples over {1, 2,. . . k} and two n-tuples are adjacent if they are in a certain relation. These graphs are… Expand

A statistical analysis of the towers of hanoi problem

- Mathematics
- 1989

The Towers of Hanoi problem is analyzed with the aid of Hanoi graphs depicting legal configurations (i. e. arrangements of the disks on the pegs) and the transitions among them. Specifically, the… Expand

The average distance on the Sierpiński gasket

- Mathematics
- 1990

SummaryThe canonical distance of points on the Sierpiński gasket is considered and its expectation deduced. The solution is surprising, both for the value and for the method derived from an analysis… Expand

On the Frame-Stewart algorithm for the multi-peg Tower of Hanoi problem

- Computer Science, Mathematics
- Discret. Appl. Math.
- 2002

It is proved that seven different approaches to the multi-peg Tower of Hanoi problem are all equivalent. Among them the classical approaches of Stewart and Frame from 1941 can be found.

The Tower of Hanoi: A historical survey and bibliography

- version 0.2. Preprint
- 2001

The Tower of Hanoi. Algebras and Combinatorics (ICAC'97, Hong Kong)

- The Tower of Hanoi. Algebras and Combinatorics (ICAC'97, Hong Kong)
- 1999

Graphs S(n

- k) and a variant of the Tower of Hanoi problem. Czechoslovak Math. J. 47 (122), 95–104
- 1997