The Never Ending Towers of Hanoi |
· There are three pegs: A, B and C.
· There are n disks. The number n is constant while working
the puzzle.
· All disks are different in size.
· The disks are initially stacked on peg A so that they increase
in size from the top to the bottom.
· The goal of the puzzle is to transfer the entire tower from
the A peg to the peg C.
· One disk at a time can be moved from the top of a stack either
to an empty peg or to a peg with a larger disk than itself on the top of
its stack.
Your job will be to write a program which will show a copy of the puzzle on the screen step by step, as you move the disks around. This program has to solve the problem in an efficient way.
TIP: It is well known and rather easy to prove that the minimum number
of moves needed to complete the puzzle with n disks is 2^n -1.
Problem #1 A=> 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 B=> C=> A=> 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 B=> C=> A=> 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 B=> C=> Problem #2 A=> 8 7 6 5 4 3 2 1 B=> C=> A=> 8 7 6 5 4 3 2 B=> 1 C=> A=> 8 7 6 5 4 3 B=> 1 C=> 2 A=> 8 7 6 5 4 3 B=> C=> 2 1 A=> 8 7 6 5 4 B=> 3 C=> 2 1 A=> 8 7 6 5 4 1 B=> 3 C=> 2 A=> 8 7 6 5 4 1 B=> 3 2 C=> A=> 8 7 6 5 4 B=> 3 2 1 C=> A=> 8 7 6 5 B=> 3 2 1 C=> 4 A=> 8 7 6 5 B=> 3 2 C=> 4 1 A=> 8 7 6 5 2 B=> 3 C=> 4 1 A=> 8 7 6 5 2 1 B=> 3 C=> 4 A=> 8 7 6 5 2 1 B=> C=> 4 3 A=> 8 7 6 5 2 B=> 1 C=> 4 3 A=> 8 7 6 5 B=> 1 C=> 4 3 2 A=> 8 7 6 5 B=> C=> 4 3 2 1 A=> 8 7 6 B=> 5 C=> 4 3 2 1 A=> 8 7 6 1 B=> 5 C=> 4 3 2 A=> 8 7 6 1 B=> 5 2 C=> 4 3 A=> 8 7 6 B=> 5 2 1 C=> 4 3 A=> 8 7 6 3 B=> 5 2 1 C=> 4 A=> 8 7 6 3 B=> 5 2 C=> 4 1 A=> 8 7 6 3 2 B=> 5 C=> 4 1 A=> 8 7 6 3 2 1 B=> 5 C=> 4 A=> 8 7 6 3 2 1 B=> 5 4 C=> A=> 8 7 6 3 2 B=> 5 4 1 C=> A=> 8 7 6 3 B=> 5 4 1 C=> 2 A=> 8 7 6 3 B=> 5 4 C=> 2 1 A=> 8 7 6 B=> 5 4 3 C=> 2 1 A=> 8 7 6 1 B=> 5 4 3 C=> 2 A=> 8 7 6 1 B=> 5 4 3 2 C=> A=> 8 7 6 B=> 5 4 3 2 1 C=> A=> 8 7 B=> 5 4 3 2 1 C=> 6 A=> 8 7 B=> 5 4 3 2 C=> 6 1 A=> 8 7 2 B=> 5 4 3 C=> 6 1 A=> 8 7 2 1 B=> 5 4 3 C=> 6 A=> 8 7 2 1 B=> 5 4 C=> 6 3 A=> 8 7 2 B=> 5 4 1 C=> 6 3 A=> 8 7 B=> 5 4 1 C=> 6 3 2 A=> 8 7 B=> 5 4 C=> 6 3 2 1 A=> 8 7 4 B=> 5 C=> 6 3 2 1 A=> 8 7 4 1 B=> 5 C=> 6 3 2 A=> 8 7 4 1 B=> 5 2 C=> 6 3 A=> 8 7 4 B=> 5 2 1 C=> 6 3 A=> 8 7 4 3 B=> 5 2 1 C=> 6 A=> 8 7 4 3 B=> 5 2 C=> 6 1