For reference, the link I posted was about the following snippet...
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