Time complexity of the Towers of Hanoi problem. (English) Zbl 0621.68029

SIGACT News 18, No. 1, 80-88 (1986).
The authors discuss two problems connected with the Towers of Hanoi Problem in N discs and 3 towers. Both problems concern move sequences with the minimal number of moves (which is known to be equal to \(2^ N- 1\) for the standard problem of transferring all the discs from one tower to another). The first problem is, given a number \(k\leq 2^ N-1\), to determine the k-th move in the minimal move sequence for the standard problem. The second problem is to determine the minimal number of moves necessary to transfer a legal configuration (i.e. no disc lies on a smaller one) to another legal one. Both problems can be solved in O(N) time.
Reviewer: D.Yu.Grigorev


68Q25 Analysis of algorithms and problem complexity


Towers of Hanoi