[comp.theory] Non recursive "Towers of Hanoi"

diderich@disun17.epfl.ch (Claude Diderich) (11/26/90)

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.

Send replies to "diderich@eldi.epfl.ch" or post them to the net. Thanks
in adavnce for youe numerous replies.

Claude G.Diderich

-------------------------------------------------------------------------------
Claude G.Diderich                  Internet: diderich@eldi.epfl.ch
30, Avenue S.Reymondin             Chadnet:  ELDI::DIDERICH
CH-1009 Pully                      Hepnet:   20550::DIDERICH (PSICLU::DIDERICH)
Switzerland - Europe
-------------------------------------------------------------------------------

00lhramer@bsu-ucs.uucp (Only to fly where angels dare - and the nights she whispers - Ride the wind never coming back again...) (11/26/90)

> 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.
> 
> Send replies to "diderich@eldi.epfl.ch" or post them to the net. Thanks
> in adavnce for youe numerous replies.

I'm not sure whether my idea follows the constraints or not, but here goes.
Every other move, you need to move the smallest disk to the right.
Simple enough right?  When you get all the way to the right and it comes
time to move it again, you move it back to the far left.  I guess you could
call this a rotation.  Anyway, there is only one legal move in between each
of the movements of the small disk.

This certainly follows the iterative constraint number 2.
The number of iterations is and will always end up (2**n)-1
The data storage could be three stacks.  I imagine this would make it O(n).
There should be patterns emerging like crazy, and maybe this algorithm could
be generalized by this idea.

Another idea that I "developed" on my experimentation was to represent this
all in some sort of binary scheme.  I decided I would generalize the movements
by representing the movements with zeros and ones.  I modeled the tower that
I would take a piece from with a one and the destination tower with another
one.  The remaining "spare" tower ends up being zero.  Logically there is
only one legal move with the two ones.  A pattern starts to emerge.

imagine all the disks are stored on the far left tower.
The numbering scheme for the solution that I used looks something like this:

110 <------+  Notice a pattern emerging?
101        |  I leave this to the readers to achieve the storage constraint
011        |  of O(1).  I have an exam to study for.  From my experimentation
110 <------+  I don't know whether I can prove that its possible for that
101        |  amount of data storage.
011        |
110 <------+ 
101
011

i.e. -

ABC
110 A->B (solution for one disk puzzle)     (moves=1=[2**1]-1)
101 A->C
011 B->C (solution for two disk puzzle)     (moves=3=[2**2]-1)
110 A->B
101 C->A
011 C->B
110 A->B (solution for three disk puzzle)   (moves=7=[2**3]-1)
101 A->C
011 B->C
110 B->A
101 C->A
011 B->C
110 A->B
101 A->C
011 B->C (solution for four disk puzzle)    (moves=15=[2**4]-1)
 .   .
 .   .
 .   .

Commercial flash -> "Nothing outlasts the energizer, it goes on, and on..."
(Just couldn't resist it.  Tension breaker you know.)

I don't see a big need to restrict the amount of storage space so much, though,
unless you are trying to relate this to a similar problem.  If you consider
that the Nth disk cannot be moved until the top (N-1) disks have been moved to
another tower, the problem with memory space is trivial.  Consider the 64 disk
problem.  Remember that if the monks were to move one disk a second, it would
take approximately 5.84E11 years to complete.  To ever get to the 64th disk
it would take 429,4967,295 moves.  Imagine that your computer could move
10,000 disks a second, it would still take a long time to solve, much longer
than your children's children's...children will ever get to see.  :-)  The sun
is predicted to burn out before that time, anyhow.  What's 64*3 bytes anyway?
Less than 1 page of memory.  It's an interesting question to attempt to answer
though.

I hope this helps to determine an answer to this problem.

----
Les Ramer   : (Junior) Computer Science Major
              Ball State University, Muncie, IN
e-mail addr : 00LHRAMER@BSUVAX1.BITNET

varvel@cs.utexas.edu (Donald A. Varvel) (11/27/90)

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)

lambert@cwi.nl (Lambert Meertens) (11/27/90)

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

tromp@cwi.nl (John Tromp) (11/27/90)

The following C-program solves the Towers of Hanoi problem iteratively
using the arguably minimal number of bits necessary (n bits for n discs):

main(argc,argv)
int argc;
char *argv[];
{
    int x, max;

    max = 1 << atoi(argv[1]);
    for (x = 1; x < max; x++)
        printf("move a disc from %d to %d\n", (x&x-1)%3, ((x|x-1)+1)%3);
}

for example:
$ hanoi 3
move a disc from 0 to 2
move a disc from 0 to 1
move a disc from 2 to 1
move a disc from 0 to 2
move a disc from 1 to 0
move a disc from 1 to 2
move a disc from 0 to 2
$

it moves all discs from pole 0 to pole 2 (or 1, depending on parity of n).

It is interesting to note that when we write each configuration of discs
as a sequence of n trits {0,1,2}, (pole of largest disc up to pole of
smallest disc), we effectively have a ternary Gray code.
It is quite easy to convert between this and binary notation,
thus we can compute directly the disc configuration reached after i steps.
Conversely, for a given disc configuration, we can easily compute the number
of steps from the initial configuratoin to take you there.

some other observations:
-all the odd-numbered discs move in one direction around the three poles,
while all the even-numbered discs move in the opposite direction.
-there never appears an odd-numbered disc directly on top of another
 (and similarly for even-numbered discs)

John Tromp (tromp@cwi.nl)

Bruce.Hoult@bbs.actrix.gen.nz (11/27/90)

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

Bruce.Hoult@bbs.actrix.gen.nz (11/27/90)

In article <1990Nov27.112713.26729@actrix.gen.nz> I wrote:
> 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.

Whoops!

The calculation for the number of moves left sometimes gives an overestimate
if the desired final configuration is not the standard one of all disks on
the same pile.

It isn't immediately obvious to me how to correct this, although I think one
way would be to remove the multiply-by-2 part of the calculation, and add an
extra loop that calculated the number of moves from the desired final position
to the position with "diskToMove" having been moved and all smaller disks on
"pileSpare" (this is symmetrical to what will actually be done).

chisnall@cosc.canterbury.ac.nz (The Technicolour Throw-up) (11/28/90)

From article <1197@disuns2.epfl.ch>, by diderich@disun17.epfl.ch (Claude Diderich):
> 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.

You can find such an algorithm in...

"Towers of Hanoi and Analysis of Algorithms" by Paul Cull and E.F. Ecklund,Jr.
American Math. Monthly 92 (1985), pp407-420


--
 Name:    M. D. Chisnall
 Address: chisnall@cosc.canterbury.ac.nz
 Fax:     Just them, Ma'm, nothing else
 Quote:   Are funky programming languages based on the lambada calculus?

dking@ut-emx.uucp (David L. King) (12/04/90)

I'm afraid this takes some of the recursive fun out of the tower of Hanoi
puzzle, but an optimal solution simply does the following:

Every other move, the smallest one moves, in a consistent cyclic direction
(i.e., either 1->2->3->1->2....  or 1->3->2->1...)

On the other move, do not move the smallest one -- there will be only one
possibility.

Getting the correct initial move for general positions is not too hard,
once you realize that each disk moves 1/2 as often as its next-smaller
disk, and in the opposite cyclic direction (in a kind of grey-code).  You
look at the largest disk that is not in its goal position, and its cyclic
direction in the fastest solution would take it immediately to its goal
position.  This gives correct directions for all other disks, including
the smallest one.  If there is another possibility for the first move
besides moving the smallest one, take it iff it is in the correct cyclic
direction.


					David L. King <dking@chpc.utexas.edu>
					University of Texas System
					Center for High Performance Computing

dking@ut-emx.uucp (David L. King) (12/04/90)

Postscript to the last post.  I take it back: finding the fastest solution
is not as easy as I said, in general cases.  The algorithm IS fastest where
all are initially on one post.  But positions can arise in which it would not
be the smallest one's 'turn', yet only the smallest one can move (all have been
stacked on one post).  In this case move the smallest again (in the same old
indicated direction) and you will be on the quickest road from where you are
currently.  I.e, the algorithm gets you there in any case.  However, the
fact that you moved one disk twice to where it could be moved in
one move shows that it is not the fastest solution in these cases.
I'll let others use that archetypal case to arrive at the ultimate solution.
It's still not very hard, but there's a little fun left....


					David L. King <dking@chpc.utexas.edu>
					University of Texas System
					Center for High Performance Computing

shallit@graceland.waterloo.edu (Jeffrey Shallit) (12/07/90)

In the recent discussion about the Tower of Hanoi problem, I was
surprised to see no one mention the recent article

J.-P. Allouche and F. Dress, Tours de Hanoi et automates,
RAIRO Informatique Theorique et Applications 24 (1990), 1-15.

This article shows that the sequence of moves in the problem can
be computed by a finite automaton (!), and the automaton is
exhibited.  The input is the move number, represented in base 2,
and the output is the move.

Jeff Shallit
University of Waterloo