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

Discussion in 'C Programming' started by bagratte, Feb 20, 2012.

1. ### bagratteGuest

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?

bagratte, Feb 20, 2012

2. ### NoobGuest

Re: iterative towers of hanoi using only elementary data types

bagratte wrote:

> 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

Noob, Feb 20, 2012

3. ### Eric SosmanGuest

On 2/20/2012 9:08 AM, bagratte wrote:
> [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[4], 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.

--
Eric Sosman
d

Eric Sosman, Feb 20, 2012
4. ### BartCGuest

"bagratte" <> wrote in message
news:14882925.6018.1329746907715.JavaMail.geo-discussion-forums@vbbed8...
> 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.

--
Bartc

BartC, Feb 20, 2012
5. ### NoobGuest

BartC wrote:

> 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.

Noob, Feb 20, 2012
6. ### BartCGuest

"Noob" <root@127.0.0.1> wrote in message news:jhtqa2\$uoi\$...
> BartC wrote:
>
>> 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?

--
Bartc

BartC, Feb 20, 2012
7. ### Paul NGuest

On Feb 20, 2:08 pm, bagratte <> wrote:
> 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.

Paul N, Feb 20, 2012
8. ### BartCGuest

"Paul N" <> wrote in message
news:...
> On Feb 20, 2:08 pm, bagratte <> wrote:
>> 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.

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

--
Bartc

BartC, Feb 20, 2012
9. ### LiviuGuest

"bagratte" <> wrote...
>
> 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

Liviu, Feb 21, 2012
10. ### bagratteGuest

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.

bagratte, Feb 21, 2012
11. ### 88888 DihedralGuest

On Monday, February 20, 2012 10:08:27 PM UTC+8, bagratte wrote:
> 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.

88888 Dihedral, Feb 21, 2012
12. ### LiviuGuest

"bagratte" <> wrote...
>
> 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

Liviu, Feb 22, 2012
13. ### Edward A. FalkGuest

In article <14882925.6018.1329746907715.JavaMail.geo-discussion-forums@vbbed8>,
bagratte <> wrote:
>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.

--
-Ed Falk,
http://thespamdiaries.blogspot.com/

Edward A. Falk, Feb 22, 2012
14. ### Keith ThompsonGuest

Re: iterative towers of hanoi using only Â°elementaryÂ° data types

(Edward A. Falk) writes:
> In article <14882925.6018.1329746907715.JavaMail.geo-discussion-forums@vbbed8>,
> bagratte <> wrote:
>>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.

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.

--
Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
Will write code for food.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Keith Thompson, Feb 22, 2012
15. ### Kaz KylhekuGuest

Re: iterative towers of hanoi using onlyÂ°elementaryÂ° data types

On 2012-02-22, Edward A. Falk <> wrote:
> In article <14882925.6018.1329746907715.JavaMail.geo-discussion-forums@vbbed8>,
> bagratte <> wrote:
>>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.

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

Kaz Kylheku, Feb 22, 2012
16. ### BartCGuest

"Liviu" <0m> wrote in message
news:4f44626c\$0\$2324\$c3e8da3\$...
> "bagratte" <> wrote...

>> 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.

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.

--
Bartc

BartC, Feb 22, 2012
17. ### LiviuGuest

"BartC" <> wrote...
> "Liviu" <0m> wrote...
>> "bagratte" <> wrote...

>
>>> 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.

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

Liviu, Feb 22, 2012