Sign in to follow this  
GameDweeb

Towers of Hanoi iterativly

Recommended Posts

Okay, so I've got this problem in my programming class. I've got to come up with a non-recursive solution to the Towers of Hanoi. I'm getting stumped, I see a vague pattern in how you move the disks, depending on whether it's an odd or an even total. But I'm just not understanding what I need to do exactly. Any help in explaining what I need to do or what direction I need to look in would be much appreciated!

Share this post


Link to post
Share on other sites
There is an iterative solution which does not require a stack; it's related to the algorithm for Gray coding. Number each disk from smallest to largest, solve a short tower. Write the list of disks moved in each step. Do you see anything periodic about the 1s? What about the 2s? Extend that pattern.

EDIT: If you can use a stack, tho, do. It's a lot simpler.

Share this post


Link to post
Share on other sites
I do notice a pattern with the order that the pieces move in. it woule be easy enough to extend it indefinetly.

1,2,1,3,1,2,1,4,1,2,1,3,1,2,1 etc. etc.

I'm not sure what I'd need to write, seems like there'd need to be some if statements involved to get things to work right, but that might only be if I wanted to add user interactivity.

Here's another question though...

Can anyone help me understand the logic behind this:

int hanoi(int n, int src, int aux, int dst) {
if (n == 0) {
return 0;
}

hanoi(n-1, src, dst, aux);
cout << n << " " << src << " -> " << dst << endl;
hanoi(n-1, aux, src, dst);

return 1;
}

I put some stops in and tried to follow the logic through the debugger, but I haven't had much luck in following the logic.

I think if I can understand this more clearly I should be able to come up with a solution for the previous problem.

Share this post


Link to post
Share on other sites
Write down the binary representations of sequential integers (0001, 0010, 0011, etc) next to your list of disks. See if you can identify a correspondence.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this