Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!cica!iuvax!bsu-cs!bsu-ucs!00lhramer
From: 00lhramer@bsu-ucs.uucp (Only to fly where angels dare - and the nights she whispers - Ride the wind never coming back again...)
Newsgroups: comp.theory
Subject: Re: Non recursive "Towers of Hanoi"
Message-ID: <49714@bsu-ucs.uucp>
Date: 26 Nov 90 11:34:10 GMT
References: <1197@disuns2.epfl.ch>
Organization: Ball State University, Muncie, In - Univ. Computing Svc's
Lines: 91

> 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