Solve 4 Pegs Hanoi Tower: Algorithm & Best Move Ideas

[Stephanus]

Dear PF Forum,
Do anybody know the algorithm for 4 pegs Hanoi Tower?
In regular initial, we can use array.
But what if the initial configuration is random?
I can do it in 3 pegs, but I've been searching algorithm for 4 pegs every day, on my bed, before I go to sleep. But I can't find any.
The algorithm should find the best move. Not using "brute force"!

Thanks for any idea.

Steven

 

[Svein]

The standard way is to use a recursive algorithm:

1. 3 disks can be done directly.
2. Assume that you have found how to do it with n disks
   
   • Use this to move n disks to one of the spare pegs
   • Move the bottom disk to the goal peg
   • Move the n disks from the spare peg to the goal peg.

 

[Stephanus]

The standard way is to use a recursive algorithm:

1. 3 disks can be done directly.
2. Assume that you have found how to do it with n disks
   
   • Use this to move n disks to one of the spare pegs
   • Move the bottom disk to the goal peg
   • Move the n disks from the spare peg to the goal peg.

Yes, of course Svein. But it's not the best/shortest move is it?

 

[mfb]

According to Wikipedia, the optimal solution with 4 pegs is an unsolved problem. And randomizing the starting position certainly does not help.

 

[Stephanus]

According to Wikipedia, the optimal solution with 4 pegs http://Tower_of_Hanoi#With_four_pegs_and_beyond . And randomizing the starting position certainly does not help.

Thanks mfb,
There is, actually, an algorithm for a sorted initial position, but for a random position, well... Maybe? I've been trying for two months before I sleep. Still can't find solutions. Perhaps you're right.

 

[mfb]

(I fixed the link in the previous post)

On the positive side, if you find an efficient algorithm, you can write a paper about it.