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 | Розділити |
5 пар | 62 ходи | 88 ходів |
6 пар | 126 ходів | 183 ходи |
7 пар | 254 ходи | 374 ходи |
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.