Tower of hanoi - Alternate solution

172 views Asked by At
Label the pegs A, B, C
let n be the total number of discs
number the discs from 1 (smallest, topmost) to n (largest, bottommost)
To move n discs from peg A to peg C:

The General recursive solution is this:

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

Why can't we think of the solution this way?

Move the top disk from A to B
Move the other n-1 disks from A to C
Move the single disk from B to C

I know that the 2nd solution is wrong but I am not able to figure out the reason. Could someone please point out why the second solution is incorrect?

1

There are 1 answers

0
Abhishek Bansal On BEST ANSWER

In your second solution, you will have occupied the B peg and it shall not be available for use for the n-1 discs.

This is because you keep the smallest disk in B peg. Thus no other disc can now move on to B because all other discs are larger than it.