1

Iterative algorithm for 3 pegs (or rods, or whatever you call them) is to repeat two following points:
1. Move smallest disks to the right/left (if odd/even)
2. Make one possible move left without touching the smallest disk

My question is - Is there some similar algorithm for n > 3 pegs?

I couldn't find this in the internet (at least iterative). I couldn't figure anything out by myself. And the algorithm above just doesn't work - it moves disks inifnitely.

I know I had post 2 kind of related questions before, and you didn't welcome them too well, so before you downvote - just write me in the comment to research more for some info by myself, and I'm deleting this thread.

user2251921
  • 127
  • 10
  • 1
    You can always convert a recursive algorithm to an iterative one, by using an explicit stack. – nhahtdh Apr 08 '13 at 15:50
  • Would this be the only way, or at least the best solution? – user2251921 Apr 08 '13 at 15:51
  • Does [this](http://stackoverflow.com/questions/2870684/how-does-this-iterative-tower-of-hanoi-work-c) cover it? – Bernhard Barker Apr 08 '13 at 15:52
  • various algorithms and variations can be found on [wikipedia](http://en.wikipedia.org/wiki/Hanoi_towers) (both recursive and iterative) – msam Apr 08 '13 at 16:02
  • This isn't really a programming problem, but you could easily have found the answer in wikipedia. Questions like this (but without such an obvious way of finding an answer) would be better posted on http://cs.stackexchange.com or http://math.stackexchange.com. Anyway, I posted a corresponding answer; hope that helps. – rici Apr 08 '13 at 16:06

2 Answers2

2

The general recursive algorithm for the 3-peg Hanoi problem with n > 1 disks (the n==1 case is trivial) is:

  1. Move n-1 disks from the source peg to the third peg (the one that's not the source or target)
  2. Move the largest disk to the target peg.
  3. Move n-1 disks from the third peg to the target peg.

With more than 3 pegs, the algorithm is the same. Just replace "the third peg" with "any unused peg".

Note that the algorithm doesn't make use of terms like "move left" or "move right".

As @nhahtdh points out in a comment, any recursive algorithm can be transformed into an iterative algorithm by standard means.

Ted Hopp
  • 232,168
  • 48
  • 399
  • 521
  • 1
    This doesn't actually answer the question, which is about the `n>3`-peg problem. – rici Apr 08 '13 at 16:03
  • 1
    @rici - I explicitly talk about the n>3 peg problem; I also mention that OP can use textbook methods to convert the recursive algorithm to an iterative one. How does this not answer the question? – Ted Hopp Apr 08 '13 at 16:12
  • true, you do. Apologies. You simply don't worry about optimality or stacklessness -- O(1) space -- (the first not known for n>3; the second described in the OP for n==3), which makes your answer technically correct but, imho, unsatisfying. Not that there really is a satisfactory answer, since "No" rarely satisfies. – rici Apr 08 '13 at 16:15
1

Answer from Wikipedia article on Tower of Hanoi: No non-brute-force algorithm is known for finding a provably optimal solution, although there is an algorithm which might be optimal.

Although the three-peg version has a simple recursive solution as outlined above, the optimal solution for the Tower of Hanoi problem with four pegs (called Reve's puzzle), let alone more pegs, is still an open problem. This is a good example of how a simple, solvable problem can be made dramatically more difficult by slightly loosening one of the problem constraints.
rici
  • 234,347
  • 28
  • 237
  • 341
  • This refers only to an *optimal* solution. Merely finding *a* solution is still relatively straightforward. – recursive Apr 08 '13 at 16:07
  • @recursive: That's true. You could use the 3-peg solution, using only the first and the last two pegs, for example. But I don't think that's what the OP was looking for. – rici Apr 08 '13 at 16:08