Towers of Hanoi are ........ing me off

Hi, I made the recursive solution for the ToH problem, but I can't wrap my head around the iterative version.
I can't use vectors etc, just integer arrays or structs. Teacher gave me some clues though:

1. Always move the smallest disc first in a “clockwise” manner.
2. Then, move the smaller remaining disc onto the the other (which is the only legal move left).
3. Keep repeating this process.

I've been busy with the recursive one for almost 2 days, and now this again.. sigh.

50 views and none is answering..

First: no one guaranteed any answer!

I think you had code up earlier, but it was long. This sometimes deters people from helping (as it did when I looked earlier). I would suggest you post code, though minimal code to show what youve done. Its probably a good idea to not put all of your code if its long (as it was earlier)--just post enough to explain what youve got or enough to reproduce an error/warning/other problem. If you dont post any code or pseudocode/english description of what youve attempted, then your even less likely to get help.

Any recursive function can be implemented as an iterative function, and vice versa. This has been proven. So dont give up as there is a solution!

The hints given are pretty good. Start with a completely new file and try and understand then implement the hints. Dont try and implement anything if you dont understand it--it will only bring more confusion.

----

Originally Posted by nadroj

I think you had code up earlier, but it was long. This sometimes deters people from helping (as it did when I looked earlier)

Originally Posted by nadroj

The hints given are pretty good. Start with a completely new file and try and understand then implement the hints.

It seems youve ignored both of my suggestions. If your confused, its because your trying to convert your existing recursive solution to an iterative one, which is probably hard to do. You arent working on a recursive approach anymore, your re-doing the solution using an iterative approach. Start over. Ignore what youve done for the recursive one, look at the hints which I think are pretty good, and give it a shot. Post your attempt at the iterative approach and let us know when your stuck.

EDIT: Also, the code youve given and suggested we look at call functions that you havent included, so we dont know what it does. I wouldnt look at it even if you did post it. Though maybe others would, of course. Dont take anything personal if Im sounding harsh, because Im not trying to. Hopefully you understand, given that Ive already attempted to help and youve apparently completely ignored it. Should I spend more time "helping"?

I'm sorry for ignoring your advice, I just don't know where to begin, so starting from my recursive code seems logical.

Ok, I would guess you would have to transfer first the smallest disc, and then make the only move that is possible. And keep switching this. But you also have to switch the rotation of the transfer in the process. And stop the program when all discs are in order. Would it be good to use structs or integer arrays?

If you are using, say, n discs and t towers, then have t arrays, each of length n. So say theres 5 discs and 3 towers, create 3 int arrays, each of length 5. Initialize one of the towers to have values that are decreasing, say 5 down to 1 or 4 down to 0 (which might make understanding things easier, since the arrays are 0 based and go from 0 to 4). If a disc is on a tower, its position in the tower is the same as its index, any other values are, say, -1 or whatever. If you need to keep track of how many discs are on each tower you could even use the 1st element (index [0]) to store how many discs are there. This way you dont have to work with the discs being 0-based, just worry about indices 1-5, and 0 is, again how many on that tower (if you need this).

And keep with the given hints:

1. Always move the smallest disc first in a “clockwise” manner.
2. Then, move the smaller remaining disc onto the the other (which is the only legal move left).
3. Keep repeating this process.

So the very first iteration has no choice but to move tower1[5] (last disc which is the smallest because its on top) to, say, tower2[1] (if doing 1-based, as described above). Then, again your only option is to move tower1[4] to tower3[1].

Dont overcomplicate things with tons of functions, variables, structs (dont really need any structs, I dont think), and tons of arguments to any functions. Since this is an iterative approach, you shouldnt need many functions.

I think the best thing to do is to ignore programming (or at least that specific to any language, say C++). Grab a piece of paper, or better yet, the TOH puzzle itself! And try and work on the mechanical details that you as a person would do to solve this. Try and formalize what your doing. Then take this and transfer it to C++. The programming part is the easiest part of any problem.

Code:

    int y ( 1 );
    int x = 2^discs;
    for ( int i = 1 ; i < x ; i++ )
    {
        if ( i & 1 )
        {
            if ( y == 3 )
            {
                gold_discs--;
                copper_discs++;
                copper_rod [ copper_discs ] = 1;
                y = 2;
            }
            else
            {
                if ( y == 1 )
                {
                    copper_discs--;
                    silver_discs++;
                    silver_rod [ silver_discs ] = 1;
                    y = 3;
                }
                else
                {
                    silver_discs--;
                    gold_discs++;
                    gold_rod [ gold_discs ] = 1;
                    y = 1;
                }
            }
        }
        else
        {
            make only legal move left;
        }
    }

I think I've got the algorithm in my head, is this about right?
On odd moves you set the lowest disc to A -> B -> C -> A -> .. and on the even moves you make the only legal move possible. But how could I check for that?

Hmm.. interesting. I dont have time to really think about it, Ive only been giving you some high-level hints. I must do my work now and hopefully someone can give you their time. Good luck (this isnt a reply to scare you off). You seem to be getting somewhere without my help anyway.

int x = 2^discs;

No time to dive into the logic of your program, but please note that ^ in C-style languages is bitwise xor, not exponentiation. To get "2 to the power of" you can use bit shifts.

This has been addressed quite a few times on these forums. I am sure something below should strike your fancy!

C Board - Search Results