Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

4 Pegs Hanoi Tower

  1. May 9, 2015 #1
    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. jcsd
  3. May 9, 2015 #2

    Svein

    User Avatar
    Science Advisor

    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.
     
  4. May 9, 2015 #3
    Yes, of course Svein. But it's not the best/shortest move is it?
     
  5. May 9, 2015 #4

    mfb

    User Avatar
    2016 Award

    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
  6. May 9, 2015 #5
    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
  7. May 9, 2015 #6

    mfb

    User Avatar
    2016 Award

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: 4 Pegs Hanoi Tower
  1. Euler to Runge-Kutta 4 (Replies: 19)

Loading...