Richard Damon said:
Sort of depends on your goal.
Towers of Hanoi with 3 poles has (as I remember) a unique solution
(you could create other possible answers but they are clearly
inferior having extra redundant moves).
With a 4th pole, there are now a lot of choices. You could of
course ignore the extra pole and solve it just as the 3 pole
version. You can due "better" (in less moves) than this using the
extra pole. There are lots of options for how to do this, some
probably better than others.
In words, the method to solve the Tower of Hanoi (for 3 poles) is:
To move the pile of disks from size 1 to N from A to B (C being the 3rd)
1) First move the pile of disks from size 1 to N-1 from A to C
2) Move disk of size N from A to B
3) Move the pile of disks from size 1 to N-1 from C to B
(Note that steps 1 and 3 are where the recursion happens).
With 4 piles, step 1 can become move the pile of disks from size 1
to N-1, in some combination, to piles C and D. Note that depending
on what has previously been done, there may be limits which pile a
given disk can go to. This complication doesn't happen on the 3
pole version as it can be shown that when you are moving the size N
disk from A to B, all disks of size less than N are on C (as they
must be to do the move).
With 4 (or more) poles, you have choices, and having all the smaller
disks on a given pole is not needed, and may not be optimal.
If you aren't concerned about finding the "best" solution (minimum
moves), you can do better than the 3 pole version by reducing the
strength of recursion by changing 1 to something like:
1A) Move pile of disks from size 1 to N-2 from A to C
1B) Move disk of size N-1 from A to D
and step 3 to
3A) Move disk of size N-1 from D to B
3B) Move pile of disks from size 1 to N-2 from C to B
There is a fairly simple good solution, with pseudocode
hanoi4( n, a, b, c, d ){
if n < 3 : hanoi3( n, a, b, d ), return
choose appropriate k between 0 and n-1
hanoi4( k, a, b, d, c )
hanoi3( n-1-k, a, c, b )
move 1 disk from a to d
hanoi3( n-1-k, b, a, d )
hanoi4( k, c, a, b, d )
}
hanoi3( n, a, b, c ){ ... }
The choice of k can be made easily using the following table
and picking a k to minimize the number of moves need for
hanoi4( k, ... ) plus hano3( n-k-1, ... ).
disks moves needed for hanoi4
--------------------------------
0 0
1 1
2 3
3 5
4 9
5 13
6 17
7 25
8 33
9 41
10 49
11 65
12 81
etc
(If the pattern isn't obvious, take row-by-row differences
of the number of moves needed.)
I belive this solution is optimal but I haven't proved that.
Exercise for the reader.
