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