Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!varvel
From: varvel@cs.utexas.edu (Donald A. Varvel)
Newsgroups: comp.theory
Subject: Re: Non recursive "Towers of Hanoi"
Keywords: Towers of Hanoi, Recursivity, Storage
Message-ID: <15101@cs.utexas.edu>
Date: 26 Nov 90 19:17:42 GMT
References: <1197@disuns2.epfl.ch|>
Organization: U. Texas CS Dept., Austin, Texas
Lines: 27

In article <1197@disuns2.epfl.ch|> diderich@eldi.epfl.ch (Claude Diderich) writes:
|>Dear reader,
|>
|>I would like to know if anyone knows of an algorithm for solving the "Tower of
|>Hanoi" problem using the following constraints:
|>
|>1. The algorithm is deterministic (no backtracking, etc...)
|>2. The algorithm is iterative (no recursion)
|>3. The algorithm uses at most O(1) extra storage in additon to the
|>storage      required to modelize the three piles.
|>4. The number of iterations can be determined a priori. It must be a
|>function of n, the number of disks.
|>5. The algorithm may be non-polynomial.
|>

This one has been known for a long time.  Alternate the following
two steps:

1. Move the smallest disk clockwise one pile.
2. Move a disk other than the smallest one.  (There is only
   one other legal move.)

This produces the same moves as (one version of) the usual
recursive algorithm.  It therefore meets all of the above
criteria.

-- Don Varvel (varvel@cs.utexas.edu)