Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question

closed as not a real question by Jim G., MichaelT, gnat, GlenH7, BЈовић Jun 13 '13 at 11:40

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.

4  
How is the Hanoi Tower problem too complex to simulate? If you have an example of a complex problem that you have actually faced it would be easier to help you with regards to how to tackle the problem. –  Mike Jun 13 '13 at 2:30
    
It's hard to simulate when you have n > 5. –  John Locke Jun 13 '13 at 3:26
    
Of course the trick with divide and conquer is deciding exactly where to divide. –  Greg Hewgill Jun 13 '13 at 3:29
    
How is n > 5 more difficult that n = 5 (or 4)? –  MichaelT Jun 13 '13 at 3:58
1  
You may find the SO tag towers-of-hanoi useful. –  MichaelT Jun 13 '13 at 5:39
show 4 more comments

1 Answer

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 n as an argument.

#include <stdio.h>
#include <stdlib.h>

void hanoi(int n, const char* from, const char* to, const char* temp)
{
    if (n == 1)
    {
        printf("Move disk 1 from %s to %s.\n", from, to);
    }
    else
    {
        // Move n-1 sized stack to temporary location
        hanoi(n - 1, from, temp, to);

        printf("Move disk %d from %s to %s.\n", n, from, to);

        // Move n-1 sized stack from temp location to destination
        hanoi(n - 1, temp, to, from);
    }
}

int main(int argc, char* argv[])
{
    if (argc < 2)
        return -1;

    int n = atoi(argv[1]);

    hanoi(n, "left", "right", "middle");

    return 0;
}
share|improve this answer
    
There are many steps involved so writing a code for it is quite hard. I can solve the problem by hand with no problem. –  John Locke Jun 14 '13 at 22:56
    
It's not as simple as you make it out to be. You don't just move the nth disk to its destination, there are intermediary steps you have to consider; otherwise, developing an algorithm for it would be very simple. –  John Locke Jun 14 '13 at 23:39
2  
It is as simple as that, and I've added working code to my answer that shows it. Feel free to test it. The intermediary steps are all handled by trusting that it works for n-1. –  Karl Bielefeldt Jun 15 '13 at 3:46
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.