Any tips in tackling extremely complex problems like the Hanoi Tower problem? [closed]

Question

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?

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 n^th 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 n^th 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;
}