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?

  • 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
    Commented Jun 13, 2013 at 2:30
  • It's hard to simulate when you have n > 5.
    – John Locke
    Commented Jun 13, 2013 at 3:26
  • Of course the trick with divide and conquer is deciding exactly where to divide. Commented Jun 13, 2013 at 3:29
  • How is n > 5 more difficult that n = 5 (or 4)?
    – user40980
    Commented Jun 13, 2013 at 3:58
  • 1
    You may find the SO tag towers-of-hanoi useful.
    – user40980
    Commented Jun 13, 2013 at 5:39

1 Answer 1


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);
        // 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;
  • 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
    Commented Jun 14, 2013 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
    Commented Jun 14, 2013 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. Commented Jun 15, 2013 at 3:46

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