Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!sdd.hp.com!ucsd!ucbvax!bloom-beacon!eru!hagbard!sunic!mcsun!hp4nl!charon!lambert
From: lambert@cwi.nl (Lambert Meertens)
Newsgroups: comp.theory
Subject: Re: Non recursive "Towers of Hanoi"
Message-ID: <2594@charon.cwi.nl>
Date: 27 Nov 90 00:11:29 GMT
References: <1197@disuns2.epfl.ch>
Sender: news@cwi.nl
Reply-To: lambert@cwi.nl (Lambert Meertens)
Organization: CWI, Amsterdam
Lines: 122

In article <1197@disuns2.epfl.ch> diderich@eldi.epfl.ch (Claude Diderich)
writes:
) 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.

Several such solutions have been published in the literature (sorry, I have
no references available, but check old copies of Information Processing
Letters).

It is a good thing that the algorithm may be non-polynomial, since solving
the puzzle for n disks requires 2**n-1 moves.

The following solution, which I have never seen published, differs from all
solutions I have seen in that it is "stateless" (in the sense that the only
state information needed to determine the next move is where the disks
are).  It is essentially of the form:

   WHILE NOT final.solution.reached:
      DO.ONE.MOVE

It works from *any* starting position, always doing the optimal move.  In
the program, the disks are numbered 1 to n, and the pegs are A, B and C,
with C the "destination" peg.  The fact that disk d is on peg p is recorded
by setting peg[d] = p.  The program starts by creating a random initial
position.

   HOW TO TOH n: \Towers of Hanoi with n disks
      SET.UP
      RANDOM.STARTPOS
      WHILE NOT final.solution.reached:
         DO.ONE.MOVE
   SET.UP:
      PUT {1..n} IN disks
      PUT min disks, max disks IN small.disk, big.disk
      PUT {"A"; "B"; "C"} IN pegs
      PUT max pegs IN destination.peg
   RANDOM.STARTPOS:
      PUT {} IN peg
      FOR d IN disks:
         PUT choice pegs IN p \random choice
         WRITE "Disk `d` on `p`" /
         PUT p IN peg[d]
      WRITE /
   final.solution.reached:
      REPORT EACH dd IN disks HAS peg[dd] = destination.peg
   DO.ONE.MOVE:
      \Find and effect one step towards the goal, where
      \the goal is to get all disks to the destination peg
      PUT big.disk, destination.peg IN d, p
      WHILE 1 = 1: \i.e. "infinite" loop
         \The goal is to get all of {small.disk..d} to p
         WHILE peg[d] = p:
            \Goal can be reached by getting {small.disk..d-1} to p
            PUT d-1 IN d
         \OK, d is not on p; new goal is to move d to p
         IF legal.move:
            WRITE "Move `d` to `p`" /
            PUT p IN peg[d]
            QUIT \break from loop
         \The goal cannot be directly reached.  So replace the goal by that
         \of moving the disks that block the move d->p to the "third" peg
         PUT third.peg, d-1 IN p, d
   legal.move:
      \Can d be moved to p?  Only if each smaller disk is
      \on the "third" peg
      REPORT EACH dd IN {small.disk..d-1} HAS peg[dd] = third.peg
   third.peg:
      \This uses the fact that expressions have
      \no side effects in ABC
      REMOVE p FROM pegs
      REMOVE peg[d] FROM pegs
      RETURN min pegs

Sample output:

   >>> TOH 3
   Disk 1 on C
   Disk 2 on C
   Disk 3 on B

   Move 1 to B
   Move 2 to A
   Move 1 to A
   Move 3 to C
   Move 1 to B
   Move 2 to C
   Move 1 to C

More sample output:

   >>> TOH 7
   Disk 1 on A
   Disk 2 on C
   Disk 3 on A
   Disk 4 on C
   Disk 5 on C
   Disk 6 on C
   Disk 7 on C

   Move 2 to B
   Move 1 to B
   Move 3 to C
   Move 1 to A
   Move 2 to C
   Move 1 to C

I am not quite sure if this meets requirement 4.  It is possible to
determine a priori *upper bounds* on the number of iterations for all
loops, but the actual number for the inner loops depends of course on the
current situation, and that for the outer loop on the starting position.

--

--Lambert Meertens, CWI, Amsterdam; lambert@cwi.nl