Velocity Reviews > iterative towers of hanoi using only °elementary° data types

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

88888 Dihedral
Guest
Posts: n/a

 02-21-2012
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.

Liviu
Guest
Posts: n/a

 02-22-2012
"bagratte" <(E-Mail Removed)> 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

Edward A. Falk
Guest
Posts: n/a

 02-22-2012
In article <14882925.6018.1329746907715.JavaMail.geo-discussion-forums@vbbed8>,
bagratte <(E-Mail Removed)> 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://www.velocityreviews.com/forums/(E-Mail Removed)
http://thespamdiaries.blogspot.com/

Keith Thompson
Guest
Posts: n/a

 02-22-2012
(E-Mail Removed) (Edward A. Falk) writes:
> In article <14882925.6018.1329746907715.JavaMail.geo-discussion-forums@vbbed8>,
> bagratte <(E-Mail Removed)> 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) (E-Mail Removed) <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"

Kaz Kylheku
Guest
Posts: n/a

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

BartC
Guest
Posts: n/a

 02-22-2012
"Liviu" <(E-Mail Removed)0m> wrote in message
news:4f44626c\$0\$2324\$c3e8da3\$(E-Mail Removed) b.com...
> "bagratte" <(E-Mail Removed)> 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

Liviu
Guest
Posts: n/a

 02-22-2012
"BartC" <(E-Mail Removed)> wrote...
> "Liviu" <(E-Mail Removed)0m> wrote...
>> "bagratte" <(E-Mail Removed)> 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