Tower of Hanoi Variation

[tow3lie]

Hello,software comrades!
I have a task to do, and I have figured some part of it,but I have troubles with it.So i am writing and asking for some advice.
The task is as it follows: You are to create a program (C++ language) in which u enter a number (preferably between 5-10) and it creates some disks and numbers them between 1 and the entered number( it has to be even).Then in separates the disks with even and uneven numbers.We are given 3 poles -A,B,C. On pole A we have all disks with even number(the biggest numbers is at the bottom whereas the lowest on top) and on pole B we have the ones with uneven number.The program is to switch the places on the disks ,meaning that pole A should contain the uneven and pole B the even. We can move 1 disk per turn and we can NOT put a bigger number disk on top of a smaller one.It has to print out the number of moves it will require to do the above.

I have solved the task using real life disks and poles,and analyzed it a bit,but i have some trouble with creating the algorithm for making it.So I am asking you guyz for some help with creating that algorithm.Or if u have any ideas please share them.
Thanks in advance!

[tow3lie]

I can post ,if u want it, the solution for 6 diskis and 4 diskis

[raptr_dflo]

Well, since you know how to solve the problem for 4 and 6 disks, think about what are the legal and illegal moves, from the current state, and especially which pairs of moves make no sense (moving a disk from A to B and back to A accomplishes nothing).

To do this, you will need to represent the current state of which disks are on which pole (in which order, though by the rules the order should always be smallest on top, increasing towards the bottom), what move was just made (so you don't undo it), what moves are allowable next, and the brain power you used to solve the 4- and 6-disk problems by hand. So you may want to have classes like Game and Move. A Disk class probably isn't needed (an int is sufficient), same for a separate Pole class (you can use a std::vector<> and add and remove items only from one end).

The "algorithm" for moving the disks is just what you figured out. Say it out loud to yourself as you do it: for each disk you move, why are you moving that one instead of another one? Why are you moving it to the pole you've chosen instead of the other option? It should almost code itself....

Good luck!

[tow3lie]

Thanks! Going to try it right away.

[MareoRaft]

Is your assignment to actually find the moves to switch the tower, or simply to find the NUMBER or moves necessary?

If you only need the NUMBER of moves, then you should be able to derive a formula for it, and no programming is really necessary.

If you need to find and record an actual solution, then I suggest looking at the following:

Suppose you have a stack of 3 disks on pole A (3,2,1), and nothing on B nor C.
What pattern must you follow to move the disks to pole B?

Suppose you have a stack of 4 disks on pole A (4,3,2,1), and nothing on B nor C.
What pattern must you follow to move the disks to pole B?

Assuming we know how to move 3 disks, the solution to the 4 disk problem is easy. Just use the 3 disk pattern to move everything to pole C, then move 4 to pole B, then use the 3 disk pattern to move everything to pole B.

So you see that moving a stack of disks (n, n-1, ..., 1) can be solved recursively.

So in your program, you will have to first move disks around. Often you will run into a case where you have a stack (1, 2, ..., n) that you want to transfer to another pole. Whenever that occurs, you can call on your handy recursive function.

Once you have moved the two largest disks into their correct position, how do you put everything else back? Well, it turns out that putting everything back is like putting everything together backwards, except this time you have a BAC orientation instead of the original ABC orientation.