Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!ut-emx!dking
From: dking@ut-emx.uucp (David L. King)
Newsgroups: comp.theory
Subject: Re: Non recursive "Towers of Hanoi"
Summary: Tower of hanoi -- simple iterative solution.
Keywords: Towers of Hanoi, Recursivity, Storage
Message-ID: <40604@ut-emx.uucp>
Date: 3 Dec 90 20:00:05 GMT
References: <1197@disuns2.epfl.ch> <1990Nov27.112713.26729@actrix.gen.nz>
Organization: The University of Texas at Austin; Austin, Texas
Lines: 24


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


Brought to you by Super Global Mega Corp .com