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:, p2:, p3:[1,2], p4[3,4]. The next move is
p1:, p2:, 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
If instead we had 3 pegs the corresponding intermediate state would be
p1:, p2:, p3[1,2,3,4]. The next move is:
p1:, p2:, 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
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?