# 4 Pegs Hanoi Tower

Tags:
1. May 9, 2015

### 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

2. May 9, 2015

### 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.

3. May 9, 2015

### Stephanus

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

4. May 9, 2015

### Staff: Mentor

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

Last edited: May 9, 2015
5. May 9, 2015

### Stephanus

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.

Last edited by a moderator: May 7, 2017
6. May 9, 2015

### Staff: Mentor

(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.

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook