Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!munnari.oz.au!comp.vuw.ac.nz!actrix!Bruce.Hoult
From: Bruce.Hoult@bbs.actrix.gen.nz
Newsgroups: comp.theory
Subject: Re: Non recursive "Towers of Hanoi"
Keywords: Towers of Hanoi, Recursivity, Storage
Message-ID: <1990Nov27.112713.26729@actrix.gen.nz>
Date: 27 Nov 90 11:27:13 GMT
References: <1197@disuns2.epfl.ch>
Sender: Bruce.Hoult@actrix.gen.nz (Bruce Hoult)
Organization: Actrix Information Exchange, Wellington, New Zealand
Lines: 86
Comment-To: diderich@eldi.epfl.ch

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.

Here is a simpleminded non-recursive solution method (in Pascal) that I
just thought of.  I haven't seen it before, but I doubt if I'm the
first to come up with it.
 
Program Hanoi;
 
Const
   maxDisks = 100;
 
Type
   pile = 1..3;
 
Var
   numDisks, targetDisk, diskToMove, diskToCheck, numMovesLeft, i: integer;
   pileFrom, pileTo, pileSpare: pile;
   actual, desired: array[1..maxDisks] of pile;
 
Begin
   write('How many disks? '); readln(numDisks);
   For i := 1 To numDisks Do Begin
      write('Disk ',i:1,' is on which pile? ');
      readln(actual[i]);
   End;
   writeln;
   For i := 1 To numDisks Do Begin
      write('Disk ',i:1,' should be on which pile? ');
      readln(desired[i]);
   End;
   writeln;
 
   For targetDisk := numDisks Downto 1 Do Begin
      While actual[targetDisk] <> desired[targetDisk] Do Begin
         diskToMove := targetDisk;
         pileFrom := actual[targetDisk];
         pileTo := desired[targetDisk];
         numMovesLeft := 1;
 
         For diskToCheck := targetDisk - 1 Downto 1 Do Begin
            {find the spare pile -- should use a lookup table really!}
            pileSpare := 1;
            While (pileSpare = pileFrom) Or (pileSpare = pileTo) Do
               pileSpare := pileSpare + 1;
 
            numMovesLeft := numMovesLeft*2;
            If actual[diskToCheck] <> pileSpare Then Begin
               diskToMove := diskToCheck;
               pileFrom := actual[diskToCheck];
               pileTo := pileSpare;
               numMovesLeft := numMovesLeft + 1;
            End;
         End;
 
         writeln(
            numMovesLeft:1,': Move disk ',diskToMove:1,' from pile ',pileFrom:1,
            ' to pile ',pileTo:1
         );
         actual[diskTomove] := pileTo;
      End; {clearing the way}
   End; {for each disk}
End. {Hanoi}
 
This algorithm will work for *any* legal starting and ending positions, not
just the traditional "move all disks on one pole onto another pole" problem.
It satisfies all your constraints -- in particular note that it calculates
the number of moves left as a natural part of looking for the next move.

It would also be easy to convert into an algorithm that simply prints out
the single next move, rather than all the remaining moves -- thus making it
useful as a "hint" function in an interactive game.

-- Bruce Hoult
   Bruce.Hoult@actrix.gen.nz