Towers of Hanoi

In the great temple at Benares beneath the dome which marks the center of the world, rests a brass plate in which are fixed three diamond needles, each a cubit high and as thick as the body of a bee. On one of these needles, at the creation, God placed sixty-four disks of pure gold, the largest disk resting on the brass plate and the others getting smaller and smaller up to the top one. This is the Tower of Brahma. Day and Night unceasingly, the priests transfer the disks from one diamond needle to another according to the fixed and immutable laws of Brahma, which require that the priest on duty must not move more than one disk at a time and that he must place this disk on a needle so that there is no smaller disk below it. When all the sixty-four disks shall have been thus transferred from the needle on which at the creation God placed them to one of the other needles, tower, temple and Brahmins alike will crumble into dust, and with a thunderclap the world will vanish.

Example

Consider six disks instead of 64.

Suppose the problem is to move the stack of six disks from needle 1 to needle 2.

• Part of the solution will be to move the bottom disk from needle 1 to needle 2, as a single move.
• Before we can do that, we need to move the five disks on top of it out of the way.
• After we have moved the large disk, we then need to move the five disks back on top of it to complete the solution.

We have the following process:

1. Move the top five disks to stack 3

2. Move the disk on stack 1 to stack 2

3. Move the disks on stack 3 to stack 2

Notice that part of solving the six disk problem, is to solve the five disk problem (with a different destination needle). Here is where recursion comes in.

Algorithm

	hanoi(from,to,other,number)
			-- move the top number disks
			-- from stack from to stack to
	if number=1 then
		move the top disk from stack from to stack to
	else
		hanoi(from,other,number-1,to)
		hanoi(from,to,1,other)
		hanoi(other,to,number-1,from)
	end

Ada Code

	TOT_DISK: constant INTEGER:=64;

	type int_array is array(1..TOT_DISK) of integer;

	type towers is record
		num:integer:=0;
		disk:int_array;
	end record;

	type all_towers is array(1..3) of towers;

	main_tower: all_towers;

	procedure hanoi(from,to,other,number: in integer; 								tower:in out all_towers);
	 	disk_move: integer;
		disk_loc : integer;
	begin
	     if (number=1) then
			disk_loc:= tower(from).num;
			disk_mov:=tower(from).disk(disk_loc);
			tower(from).num:=tower(from).num-1;
			put("Moving disk ");put(disk_mov);
			put(" from tower ");put(from);
			put(" to tower "); put(to);
			new_line;
			tower(to).num:=tower(to).num+1;
			disk_loc:=tower(to).num;
			tower(to).disk(disk_loc):=disk_mov;
		else
			hanoi(from,other,to,number-1,tower);
			hanoi(from,to,other,1,tower);
			hanoi(other,to,from,number-1,tower);
		end if;
	end hanoi;


	procedure main is
	begin
		for i in 1..TOT_DISK loop
			main_tower(1).disks(i):=i;
		end loop;
		main_tower(1).num:=TOT_DISK;
		hanoi(1,2,3,TOT_DISK,main_tower);
	end main;

Execution

	set TOT_DISK =3

	hanoi(1,2,3,3,main_tower);

	hanoi(1,3,2,2)	

		hanoi(1,2,3,1)	move tower 1 to tower 2

		hanoi(1,3,2,1)	move tower 1 to tower 3

		hanoi(2,3,1,1)	move tower 2 to tower 3

	hanoi(1,2,3,1)		move tower 1 to tower 2

	hanoi(3,2,1,2)

		hanoi(3,1,2,1)	move tower 3 to tower 1

		hanoi(3,2,1,1)	move tower 3 to tower 2

		hanoi(1,2,3,1)	move tower 1 to tower 2