The Tower Of Hanoi puzzle is a problem of Recursion which was invented by the French mathematician Edouard Lucas in 1883. Today we will look at its solution algorithm and also solution using PHP.

Here is what Wikipedia says about Tower of Hanoi. Read Here ->

This is a mathematical puzzle, which consists of a set of three towers (pegs) and n number of disks, with each disk of different size. The puzzle starts with all disks present in a stack in descending order from top to bottom i.e. smallest disc at the top. Here how the problem looks with n=3 disks.

There are certain rules to solve this problem:

1. You can move only one disk at a time.

2. Only the disk present at the top can be removed (FIFO method).

3. You cannot put larger disk on top of smaller disk. Example: Considering the above image,you cannot put number 3 disk on top of number 2 disk.

With n=3, this problem can be solved in total 7 moves. The minimal number of moves required to solve a Tower of Hanoi puzzle is 2 n − 1, where n is the number of disks.

Now we will look at the Algorithm to solve this problem:

In order to write the algorithm we mark three towers (pegs) as P1, P2, P3 and number of disks as n and our task is to move all the disks present at P1 to P2.

First Condition: If there is only one disk i.e. if n=1, then it can be simply moved from P1 to P2.

Second Condition: If two disks are available i.e. if n=2, then:

1. Move the smaller (top) disk to P3.

2. Then, move the larger (bottom) disk to P2.

3. Finally, move the smaller disk from P3 to P2.

Now, The Algorithm for n number of disks can be designed as:

1 2 3 4 5 6 7 8 9 10 11 12 13 | START Procedure Hanoi(n,P1,P2,P3) IF n == 1, THEN move disk from P1 to P2 ELSE Hanoi(n - 1, P1, P3, P2) move disk from P1 to P2 Hanoi(n - 1, P3, P2, P1) END IF END Procedure STOP |

PHP code for Tower of Hanoi Problem:

1 2 3 4 5 6 7 8 9 10 | function move($n,$P1,$P2,$P3) { if ($n === 1) { print("Move disk from pole $P1 to pole $P2"); } else { move($n-1,$P1,$P3,$P2); move(1,$P1,$P2,$P3); move($n-1,$P3,$P2,$P1); } } |

Check our more about our quiz section here->.