Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!ucbvax!bloom-beacon!eru!hagbard!sunic!mcsun!hp4nl!charon!tromp
From: tromp@cwi.nl (John Tromp)
Newsgroups: comp.theory
Subject: Re: Non recursive "Towers of Hanoi"
Message-ID: <2610@charon.cwi.nl>
Date: 27 Nov 90 11:18:14 GMT
References: <1197@disuns2.epfl.ch> <49714@bsu-ucs.uucp>
Sender: news@cwi.nl
Lines: 43


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)