Tower of Hanoi Problem with Greater Than 3 Pegs

Tower of Hanoi Problem with greater than 3 pegs

Tower of Hanoi problem was invented by a French mathematician Edouard Lucas in 1883. He was inspired by a legend that tells of a Hindu temple where the pyramid puzzle might have been used for the mental discipline of young priests. Legend says that at the beginning of time the priests in the temple were given a stack of 64 gold disks, each one a little smaller than the one beneath it. Their assignment was to transfer the 64 disks from one of the three poles to another, with one important restriction where a large disk could never be placed on top of a smaller one. The priests worked very efficiently, day and night. When they finished their work, the myth said, the temple would crumble into dust and the world would vanish.

I could find lot of programs in the www for toh with 3 pegs. My toh with 3 peg function is taken from one of the sources from the web. I extended this program to work optimally for 3 or greater than 3 pegs.

For toh with 3 pegs, there is only one possibility where the disk can be placed from the src peg (if not on dest peg), which is on the aux peg. For greater than 3 pegs, there are several possibilities where it can go (one of the remaining aux pegs). Hence we cannot get an optimal solution using the generic toh 3 peg program.

My algorithm for toh with greater than 3 pegs is as follows:

(i)Divide the total number of disks (say n) by the total number of aux pegs (say n_aux).

(ii)Call toh_n_peg function with n disks

(iii)If n == 1 move disk from src -> dest

(iv)If n_aux == 1 call toh (this is toh with 3 pegs function)

(v)Decrement n_aux by 1

(vi)Check if (n/n_aux) disks are left in src…. if no…goto (ii)

[The above algorithm [(ii) … (vi) ]will move (n/n_aux) disks from src to each of the aux peg less one]

(vii)If yes….Move all the remaining pegs from src to dest using the remaining one aux peg.

[(vii) will move the last remaining (n/n_aux) disks from src to dest.]

(viii) Lastly, move all the disks from the aux to dest in LIFO order calling the toh_n_pegs function recursively

Instruction to run the program

Tower of Hanoi for greater than 4 pegs function must be run as follows:

(load “main.lsp”)

The above command with load the main function along with all the auxiliary functions.

(main n src dest)

where n -> number of disks

src -> src peg number

dest -> dest peg number

The program will calculate total number of pegs present and total number of auxiliary pegs from the information passed to the main function.