Better Split Towers of Hanoi
Surprisingly, our solution to split the towers generates much more
moves than our solution to interleave them. As both problems are symmetric, this should not be.
Disks amount | Interleaved | Split |
5 pairs | 62 moves | 88 moves |
6 pairs | 126 moves | 183 moves |
7 pairs | 254 moves | 374 moves |
Can you make the split tower as efficient as the interleaved one?
The source of discrepancy is an inefficient problem decomposition.
Satisfied that it merely worked, we looked no futher for a better solution.
Keeping the disks of the interleaved tower in the correct order during every move is unnecessary.
In fact, we can avoid moving the interleaved tower at all.
A better problem decomposition splits the pair of disks into two colored towers as they are removed from the interleaved tower.
If someone could split the (n-1) pairs of disks beforehand, could you
split the remaining pair?
- First split the first (n-1) pairs of disks from the interleaved stack into a white tower and a black tower (calling recursively your main function).
- Then move the large white disk on its target pole.
- Then move the (n-1) smaller white disks on top of the large one.
- Then move the large black disk on its target pole.
- Then move the smaller black disks in position.