Calculate the minimum number of moves required to solve "The Tower of Hanoi" with $4$ pegs and $4$ discs.

Question

Let's say you have a variant of The Tower of Hanoi, where you have $4$ pegs and $4$ discs. The formula for $3$ pegs and $n$ discs is $2^n-1$ but how would you work out the minimum number of moves in which a variant with $4$ pegs and $4$ discs can be calculated?

At first I figuered you can just ignore one of the pegs and use the normal formula but I realized that with $4$ pegs, the tower can be solved in a less number of moves. And now I'm not sure.

Answer 1

A better upper limit: you can work the discs in pairs, moving every pair of discs to a new peg in three moves using a designated "spare" peg. So the normal $2^4-1 = 15$ moves becomes $3\times (2^2-1)=9$ moves.

Similarly with $8$ discs on $4$ pegs you should be able to solve in $3\times (2^4-1) = 45$ moves.

Answer 2

I was actually doing this in my head to pass time on an aeroplane. The formula for any tower of Hanoi where the number of pegs and number of disks is the same is: 2n+1 or “2(n-1)+3”.

So 4 pegs and 4 disks the minimum number of moves would be 9.

To visualise why; The first step ‘n-1 moves’ is where you lay them out so all pegs are holding one disk.

The second step is to move the smallest disk out of the way, place the largest disk in that position, then move the smallest disk onto the now empty spot. ‘+3’

You now have all disks on individual pegs again but this time the base is in the final position and you can put the remaining disks into the final position for one move each ‘n-1 moves’.

Bonus: (x = peg number) (Y=minimum disk moves)

If x=3 then Y=(2^n)-1

IF n is less than x then Y=2n-1. [“2(n-1)+1”]

IF n=x then Y=2n+1 [“2(n-1)+3”]

I won’t spoil the fun of working out the formula for 4 pegs on your own but I will hint that;

A) Solving for n being one greater than x is what made me realise how to solve for an arbitrary number of pegs and disks.

B) (hint hint) You can group sets of moves together and treat moving the sets as one move. Ie ‘2n-1’ is unstacking and re-stacking a set of n-disks to a new peg.

I have no mathematical background so I can’t give specific terminology but I hope this is what you were after.

Answer 3

I apologies in advance for any mistakes or miscommunications or abuse of words/terms/concepts I'm still relatively new to the field of math.

So I actually find an equation to accurately predict a closer theoretical minimum number of moves for a 4 peg game of tower of Hanoi.

Up top are the 2 equations that are needed for the main equation (the one using summation). The weird symbol that looks like a backwards F combined with L is a function I came up with as a form of short hand and is called Yodh also the variable T is just a placeholder.

Firstly to explain how to use this you must know about Yodh which takes in a function as an input and an inequality then finds the smallest value X (where X is a positive integer) that when plugged into the function allows that inequality to be true. For the purposes of 4 peg towers of Hanoi the inequality is X > D (the number of discs). The function Yodh is using in this case is f(X)=f(X-1)+X which is constrained to the values of X that are positive integers (Ex: f(1)=0+1, f(2)=1+2, ... f(7)=21+7, etc). A quick example of what the output of Yodh would be for D=21 would result in 7 since f(6)=21 but that would violate the given inequality so it must return 7 (if you desire this can be rewritten as f(T-1) <= D < F(T)). Now with that out of the way its simple plug and play. If more elaboration is needed as to how to use this here is an example.

Ex:

Number of Discs = 7

Then T = 4 since f(3) = 6 which 6 < 7 and f(4) = 10 which 10 > 7 So the main equation would look like until N = 4 Summation(2^(N-1)N) - (2^(T-1)(f(T)-D)) which results in 25. So the minimum number of moves would be 25.