Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!olivea!apple!agate!ucbvax!edinburgh.ac.uk!J.Wexler
From: J.Wexler@edinburgh.ac.uk
Newsgroups: comp.sys.transputer
Subject: Re: Was: C to Occam translator
Message-ID: <05.Oct.90.12:53:30.bst.330635@EMAS-A>
Date: 5 Oct 90 11:53:30 GMT
References: <501@skye.cs.ed.ac.uk>
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: The Internet
Lines: 32

> Just as a matter of interest, you can solve Towers of Hanoi without
> recursion, so it could be done.

You probably know this, Nick, but others may not: the non-recursive solution is
extremely simple, and it's not hard to prove all its interesting properties
either.  I think (I haven't time to verify my recollection) that it goes like
this:

1. Arrange the towers in a triangle, so that "clockwise" will have some meaning
in what follows.

2. Do repeatedly -

   2a. Move the smallest piece one place clockwise;

   2b. Exit if all pieces are on one tower;

   2c. Make any legitimate move which does not involve the smallest piece.

   (End Do)

John Wexler
Edinburgh Parallel Computing Centre

P.S. There is never a choice at move 2c.  There are alternative ways to specify
     the same move, which are more complicated to describe but lead to a
     simpler program in most sequential languages.  What I mean is that, as
     I have specified 2c, you would have to write a program which tests a choice
     of moves for legitimacy, and then makes the legitimate one.
     You can in fact predict which will be the legitimate one without doing
     the testing, but the rule is not so easy to express in a single English
     sentence.