How do we know the correct moves of Tower of Hanoi?
- by Saqib
We know that:
In case of iterative solution: Alternating between the smallest and the next-smallest disks, follow the steps for the appropriate case:
For an even number of disks:
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
For an odd number of disks:
make the legal move between pegs A and C
make the legal move between pegs A and B
make the legal move between pegs B and C
repeat until complete
In case of recursive solution: To move n discs from peg A to peg C:
move n-1 discs from A to B. This leaves disc n alone on peg A
move disc n from A to C
move n-1 discs from B to C so they sit on disc n
Now the questions are:
How did we get this two solutions?
Only by intuition?
Or by logical/mathematical computation?
If computation, how?