In terms of using the fourth peg to reduce the number of operations, the idea I have is that, when we need to move pegs aside to get to the bottom-most peg, as we move the pegs aside we should try to split the moved-aside pegs evenly over the two pegs that aren’t the destination or source pegs.
In more concrete terms:
Let’s say we have 4 pegs and disks in the state p1: [1,2,3,4,5], p2:[], p3[], p4[] and we want to get all the disks from p1 to p2. Having the fourth peg allows us to eventually achieve this intermediate state: p1:[5], p2:[], p3:[1,2], p4[3,4]. The next move is p1:[], p2:[5], p3:[1,2], p4[3,4]. Now we need to get 4 to p2. This only requires moving one disk aside - the one on top of 4, which is 3.
If instead we had 3 pegs the corresponding intermediate state would be p1:[5], p2:[], p3[1,2,3,4]. The next move is: p1:[], p2:[5], p3[1,2,3,4]. Now we need to get 4 to p2. This requires moving three disks aside - the three on top of 4, which are 1,2,3.
This shows that we can reduce number of operations by splitting moved-aside disks over 2 pegs when we have 4 pegs instead of 3 pegs.
I’d like to know if this is a correct and sufficient approach for achieving minimum operations when we have a fourth peg.
Or should I keep keep digging for a better solution?
Thanks!