People often give me the "divide and conquer" tip, but I think for some problems it's not nearly enough. The problem with such a complex problem as the Hanoi Tower problem is that you can't even simulate or abstract parts of the problems even if you divide it into parts if you know what I mean. So, can anyone give me a step-by-step approach in tackling such a complex and difficult problem?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.
Divide and conquer is about making the problem so small that it is absolutely trivial to solve. Then you make it slightly larger, and slightly larger, and look for patterns.
For Towers of Hanoi, what is the simplest possible problem? One disk, moved straight to its destination. The second simplest is two disks. First you move one disk to a temporary spot, you move the second to the destination, then you move the first disk to the destination.
The next iteration is harder, but the trick here is to recognize that you already have proved you can move a stack of two disks, so you can abstract that away. You move a stack of two to a temporary location, move the nth disk to its destination, then move the stack of two on top of it.
You now start to see a pattern emerge. For n disks, you first move a stack of n-1 disks, then the nth disk, then you move the stack on top of it. You know this is guaranteed to work, because you can define n-1 in terms of n-2, which you can define in terms of n-3, and so on until you eventually get to one disk, which is trivial.
Where people get into trouble is trying to hold every single iteration in their head at once. You have to learn to trust that it works for n-1.
Here's a complete working implementation in C. Pass in