Write an assembly language program to solve the Towers of Hanoi puzzle. The puzzle
consists of three pegs and N disks. Disk 1 is smaller than disk 2, which is smaller than
disk 3, and so on. Disk N is the largest. Initially, all N disks are on peg 1 such that the
largest disk is at the bottom and the smallest at the top (i.e., in the order N, N − 1, ...,
3, 2, 1 from bottom to top). The problem is to move these N disks from peg 1 to peg 2
under two constraints: you can move only one disk at a time and you must not place a
larger disk on top of a smaller one. We can express a solution to this problem by using
recursion. The function
move(N, 1, 2, 3)
moves N disks from peg 1 to peg 2 using peg 3 as the extra peg. There is a simple solution if you concentrate on moving the bottom disk on peg 1. The task move(N,1,2,3)
is equivalent to
move(N-1, 1, 3, 2)
move the remaining disk from peg 1 to 2
move(N-1, 3, 2, 1)
Even though the task appears to be complex, we write a very elegant and simple solution
to solve this puzzle. Here is a version in C.
void move (int n, int x, int y, int z)
{
if (n == 1)
printf("Move the top disk from peg %d to %d\n",x,y};
else
move(n-1, x, z, y)
printf("Move the top disk from peg %d to %d\n",x,y};
move(n-1, z, y, x)
}
int main (void)
{
int disks;
scanf("%d", &disks);
move(disks, 1, 2, 3);
}
Test your program for a very small number of disks (say, less than 6). Even for 64 disks,
it takes years on whatever PC you have!