It's a "little" faster when you use 4 poles instead of three... For 30 disks, it'll run a million times faster.
Strategy: move some disks from the one disk to an auxiliary.
move the remainder using the "usual" three pole algorithm
move them back.
Dynamic programming is used to decide how many to first move.
Enter the number to move in Input and press ENTER.
The Output will show how many moves it will take and a how many disks
to first move.
For example, if N = 5, we move 3 disks using 4 poles, then 2 disks
using 3 poles, then 3 disks using 4 poles.
You can STOP and START OVER the applet.
Hanoi4
contains the algorithm.
HanoiAppSwing
is the applet. It is really a subclass of InAndOutSwing
(which uses semaphores).