# iterative towers of hanoi using only °elementary° data types

B

#### bagratte

hello all,

so the question is: is there any chance to solve a generic towers of hanoi iteratively not using any kind of arrays, stacks, bit-wise wizardry etc.?

actually the problem is much wider than c language, but i just didn't know where to post. the question could be paraphrased as followed: are there any fixed number of variables by which one could represent the state of towers of hanoi?

N

#### Noob

bagratte said:
actually the problem is much wider than c language, but i just didn't
know where to post. the question could be paraphrased as followed:
are there any fixed number of variables by which one could represent
the state of towers of hanoi?

I think you want comp.programming

E

#### Eric Sosman

[reformatted for legibility]

so the question is: is there any chance to solve a generic towers of
hanoi iteratively not using any kind of arrays, stacks, bit-wise wizardry etc.?

actually the problem is much wider than c language, but i just didn't know
where to post. the question could be paraphrased as followed: are there any
fixed number of variables by which one could represent the state of towers
of hanoi?

Yes, of course. As a point of attack on the wider question,
consider doing array-like things without using arrays. Instead of
an array x, you could have free-standing variables x0,x1,x2,x3.
You could then write

/* Instead of x = y */
switch (i) {
case 0: x0 = y; break;
case 1: x1 = y; break;
case 2: x2 = y; break;
case 3: x3 = y; break;
}

/* Instead of y = x */
switch (i) {
case 0: y = x0; break;
case 1: y = x1; break;
case 2: y = x3; break;
case 4: y = x4; break;
}

The stupidity of this transformation isn't important; it just
demonstrates in a sort of "existence proof" way that one could, at
least in theory, perform array-like operations without arrays.

Once you have array operations, you can go on to build all sorts
of other data structures atop them: Stacks, lists, queues, trees,
whatever you like. (Again, think of this as an existence proof,
not as practical programming.)

Here's another existence-proof-ish demonstration that a fixed
number of variables suffices: The actual machine on which you run
your program -- any program at all -- is finite and can manage only
a fixed number of variables. (Yes, even if you "swap" variables to
I/O devices: You still need to keep track of what's where, and your
resources for record-keeping are finite.) The number of variables
a program can manage is huge, but cannot exceed some very large but
fixed limit. Ergo, QED, reductio ad nauseam, left as an exercise
for the student, et cetera.

B

#### BartC

bagratte said:
hello all,

so the question is: is there any chance to solve a generic towers of hanoi
iteratively not using any kind of arrays, stacks, bit-wise wizardry etc.?

actually the problem is much wider than c language, but i just didn't know
where to post. the question could be paraphrased as followed: are there
any fixed number of variables by which one could represent the state of
towers of hanoi?

I found this on the first page of google hits for "solve tower of hanoi":

/* Tower of Hanoi - the answer */
/* How to move four rings from pin 1 to pin 3 using pin 2 as spare */
#include <stdio.h>

void move(int n,int A,int C,int B)
/* number to move, source pole, destination pole and
spare pole respectively */
{
if (n==1){printf("Move from %d to %d.\n",A,C);}
else {move(n-1,A,B,C);move(1,A,C,B);move(n-1,B,C,A);}
}

int main(void)
{
move(4,1,3,2);
}

There are no arrays involved. The numbers of rings on each 'pole' are
presumably stored in the different levels of stack.

N

#### Noob

BartC said:
void move(int n, int A, int C, int B)
{
[...] { move(n-1,A,B,C); move(1,A,C,B); move(n-1,B,C,A); }
}

Recursion is not allowed when an iterative solution is required.

B

#### BartC

Noob said:
BartC said:
void move(int n, int A, int C, int B)
{
[...] { move(n-1,A,B,C); move(1,A,C,B); move(n-1,B,C,A); }
}

Recursion is not allowed when an iterative solution is required.

For some reason I didn't notice the word Iterative. Or Stacks. In that case
I've no idea how it could be done, for N-rings in general where no upper
limit is specified for N.

Use strings? Or does that not count as an elementary datatype? And
presumably a bitmap image is out too.

And it sounds like we can't even use elementary types, by using bits in a
number when N is 32 or 64. So what *can* we use?

P

#### Paul N

hello all,

so the question is: is there any chance to solve a generic towers of hanoi iteratively not using any kind of arrays, stacks, bit-wise wizardry etc.?

actually the problem is much wider than c language, but i just didn't know where to post. the question could be paraphrased as followed: are there any fixed number of variables by which one could represent the state of towers of hanoi?

Here's an iterative solution with a minimum number of variables:

10 PRINT "Move the smallest disk forward one peg"
20 PRINT "Make the only possible move that doesn't move the smallest
disk"
30 GOTO 10

This will move all the disks to one of the other pegs, in the minimum
number of moves, at which point you stop.

B

#### BartC

Paul N said:
Here's an iterative solution with a minimum number of variables:

10 PRINT "Move the smallest disk forward one peg"
20 PRINT "Make the only possible move that doesn't move the smallest
disk"
30 GOTO 10

This will move all the disks to one of the other pegs, in the minimum
number of moves, at which point you stop.

That uses stacks. (In the form of rings on pegs.)

L

#### Liviu

bagratte said:
so the question is: is there any chance to solve a generic towers
of hanoi iteratively not using any kind of arrays, stacks, bit-wise
wizardry etc.?

Depends on what precisely you consider "bitwise wizardry" ;-)

Don't find a handier reference now, but have a look at
http://stackoverflow.com/questions/2209860/how-does-this-work-weird-towers-of-hanoi-solution

On a hypothetic computer with native base-3 integer representation
this could possibly qualify as the "natural" answer.

Liviu

B

#### bagratte

i do find that a bit-wise wizardry.

now, the key point is in the word "generic" as with any particular configuration one could rudely figure out a number of variables that would represent the state of the pegs.

to be more precise, what is in question is to write a function, say hanoi(n), that solves iteratively the towers of hanoi of 3 pegs with n disks. it doesn't even matter if the solution is the optimal one or otherwise. but since the optimal solutions are more investigated and present i pick the firstthat i come across, the one in http://en.wikipedia.org/wiki/Tower_of_Hanoi#Simpler_statement_of_iterative_solution, right? it says:

make the legal move between pegs A and B
make the legal move between pegs A and C
make the legal move between pegs B and C
repeat until complete

all right, to move a disk from A to B i need to know what are the disks on top of the pile on each of the pegs. that gives me (at least) three variables that hold the radii of the topmost disk on respective pegs. say:

A_top, B_top, C_top.

now suppose, in some middle of the process, i am in a configuration where ihave:

(from bottom to top)
peg A: 8, 7, 6, 4, 3
peg B: 5, 2
peg C: 1

just a random improvised configuration. now to make the move between, say, peg A and peg B, i recognize that the direction is from B to A. but then i have to be able to determine that the next disk on B is the one with radius5. similarly, in an eventual case when i want to move the 4 from A to somewhere, i have to know that the next one is a generic 6 and so forth...

one could opt for representing brakes in the ordering of the disks on pegs.that would eventually give an n/2 variables per peg, which is, sadly, not fixed.

i guess it's impossible unless there is an algorithm that always generates some well structured disk ordering pattern.

so i am left to do it as christ commands and good folk obeys, i guess; using arrays.

8

#### 88888 Dihedral

hello all,

so the question is: is there any chance to solve a generic towers of hanoi iteratively not using any kind of arrays, stacks, bit-wise wizardry etc.?

actually the problem is much wider than c language, but i just didn't know where to post. the question could be paraphrased as followed: are there any fixed number of variables by which one could represent the state of towers of hanoi?
------------------------------------------------------------------------------

Solve the general difference equations first.

Then by given the initial conditions, it is trivial to generate the
solutions of all the movements of rings on the 3 to 5 rods.

This is a math problem.

L

#### Liviu

bagratte said:
i do find that a bit-wise wizardry.

Can't tell what "that" is since you snipped the entire context.

In case this was in reply to my previous post, I wouldn't necessarily
call it "bitwise wizardy", since that's only a trick of implementation.
You could write your own functions similar to "(x & (x-1)) % 3"
without relying on bit manipulations.
now, the key point is in the word "generic" as with any particular
configuration one could rudely figure out a number of variables that
would represent the state of the pegs.

I guess here lies the misunderstanding. "Solving" the Hanoi problem
does not necessarily require the program to remember the state of
the pegs at each step.

Suppose you found an algorithm to solve the problem, and you proved
it correct using (sigh) pencil and paper.

At that point, the program needs only implement the algorithm, not
the proof. And, if the algorithm gives the next move based solely on
the step number (index in the sequence of moves), then that's all that
the program needs to implement - no need to remember the whole
history of steps or state of the pegs. Unless, of course, you have
additional requirements besides just "solving" which you haven't
mentioned upfront, for example making an animation of the process.

Liviu

E

#### Edward A. Falk

hello all,

so the question is: is there any chance to solve a generic towers of hanoi iteratively
not using any kind of arrays, stacks, bit-wise wizardry etc.?

Yes, but it's not easy and it's not interesting.

The point of solving Towers of Hanoi isn't to solve the problem --
it's been solved already -- but to teach the elegance of recursion.

K

#### Keith Thompson

Yes, but it's not easy and it's not interesting.

The point of solving Towers of Hanoi isn't to solve the problem --
it's been solved already -- but to teach the elegance of recursion.

Yes, but solving an inherently recursive problem without using
recursion can also be instructive (even if the only lesson is that
recursion is better). And solving it without explicit recursion
but using stacks (which is not what the OP asked) can help in
understanding how recursion works.

K

#### Kaz Kylheku

Yes, but it's not easy and it's not interesting.

The point of solving Towers of Hanoi isn't to solve the problem --
it's been solved already -- but to teach the elegance of recursion.

And here I thought the point was to generate a delay of 585 billion years using
only 64 disks and three rods.

B

#### BartC

Liviu said:
I guess here lies the misunderstanding. "Solving" the Hanoi problem
does not necessarily require the program to remember the state of
the pegs at each step.

Suppose you found an algorithm to solve the problem, and you proved
it correct using (sigh) pencil and paper.

You mean, being able to predict the pattern of moves, without having to
'physically' move rings from one peg to another?

I think the algorithm I posted does exactly that, as it doesn't seem to need
to know the number of rings on each pole, but presumably needs the stack to
remember where it is in the algorithm.

L

#### Liviu

for (int x=1; x < (1 << nDisks); x++)
{
int FromPole = (x&(x-1))%3;
int ToPole = ((x|(x-1))+1)%3;
moveDisk(FromPole, ToPole);
}

....which does indeed solve the problem, as long as (1 << nDisks)
fits into an int.
You mean, being able to predict the pattern of moves, without having
to 'physically' move rings from one peg to another?

Yes, and without having to remember/check the state. What the above
does is essentially "decode" the next move from just the step number.
This can be proven to work correctly, so the program does not need
to verify, for example, that the "moveDisk(FromPole, ToPole)" is a
valid move within the rules, or that the last move completes the game.
Those facts have been established by proving the algorithm, and the
program needs just implement the known-good algorithm.

My other point was that "solving" the problem is the "for" loop itself.
"moveDisk" could be a user provided callback, which might use the
information to, for example, draw an animation of the process. For
that purpose, moveDisk itself may need to maintain its own internal
history of moves and layout of the pegs/disks. However, those would
be part of applying the solution, not of "solving" the problem per se.
I think the algorithm I posted does exactly that, as it doesn't seem
to need to know the number of rings on each pole, but presumably
needs the stack to remember where it is in the algorithm.

Correct on both accounts. The algorithm is provably correct, and it
does generate the optimum solution. However, it does also store
more "state" in the stack, which grows to "n" deep. The "bits trick"
only uses one bit per disk for the "x" counter (and no recursion).

Liviu