13 N TOWERS OF HANOI

Steps of the Frame–Stewart Algorithm:

* Let n be the number of disks.

* Let r be the number of pegs.

* Define T(n,r) to be the minimum number of moves required to transfer n disks using r pegs.

The algorithm can be described recursively:

1. For some k, 1<= k < n, transfer the top k disks to a single peg other than the start or destination pegs, taking T(k,r) moves.

2. Without disturbing the peg that now contains the top k disks, transfer the remaining n-k disks to the destination peg, using only the remaining r-1 pegs, taking T(n-k,r-1) moves.

3. Finally, transfer the top k disks to the destination peg, taking T(k,r) moves.

The entire process takes 2T(k,r)+T(n-k,r-1) moves. The count k should be picked for which this quantity is least.

#Frame-Stewart Algorithm For Multi-pegs Tower of Hanoi 

def nHanoi(mdisks,npegs):

    if mdisks ==0: #zero disks require zero moves

        return 0

    if  mdisks == 1 and npegs > 1: #if there is only 1 disk it will only take one move

        return 1

    if npegs == 3:#3 pegs is well defined optimal solution of 2^n-1

        return 2**mdisks - 1

    if npegs >= 3 and mdisks > 0:

        potential_solutions = (2*nHanoi(kdisks,npegs) + nHanoi(mdisks-kdisks,npegs-1) for kdisks in range(1,mdisks))

        return min(potential_solutions) #the best solution

    #all other cases where there is no solution (namely one peg, or 2 pegs and more than 1 disk)

return float("inf")

# N PEGS

N = 3

# M DISCS

M = 3

print ('Number of moves:',nHanoi(M, N))

If N =3, M=3 then output:

Number of moves: 7

If N=3, M=1 then output:

Number of moves: 1

If N=3, M=5 then output:

Number of moves: 31

If N=4 M=6 then output:

Number of moves: 17

If N=7 M=15 then output:

Number of moves: 47

If N=4 M=15 then output:

Number of moves: 129