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.