-----Solution by Padmini Mukkamal---------
you asked for a "next" for the tower of henoi problem which is not
determined recursively, but can be determined from the given situation. i
have a longish solution, but well, i have tried to describe it as best as
i could below:
the crucial thing to note is that at any stage, every block is either
waiting for all the blocks above it get removed, so that it can move to a
different pole (i will call this the "moving"/"m" block, for the lack of
any better name), or is waiting for a complete tower to build over it (i
will call this the "waiting"/"w" block). for eg, after the certain steps,
when the poles look like [],[n],[n-1,....,2,1] then n is a waiting block,
and the rest are moving blocks. at every stage, the smallest "moving"
block has to be moved. to determine the type of a particular block, start
from n. if n is on the second pole, it is waiting, otherwise it is moving.
from here onwards, proceed with the decreasing number of the blocks, if i
is "m" and i-1 is on the same pole as i and above it, then, i-1 is "m" and
"w" otherwise. proceeding thus, we can label all blocks. then find the
smallest block labelled "m". this block would have to be moved. to figure
which pole it goes to is the easier part, say i is the smallest moving
block and i,i+1,..,i+k are all moving blocks. then we know that we want
i+k to go over i+k+1 (or when i+k is n then we know we want n to go to
pole 2) hence, i+k-1 would go to the other pole, and alternating thus,
we'd eventually know which pole "i" would go to.
this is quite long and i was wondering if there was an easier way to do
it. i would be glad if you'd let me know,
regards,
padmini
--------------------