Hello , i'm trying to solve a problem Tower of Hanoi recursively. I'm having problems with coming up with logic how to treat disks in terms of value. Lets say i have 3 disks how should i assign values to them ? My function is supposed to be defined such as.

int move_disk(int disk,int peg1,int peg2,int peg3)

I don't need the code i'm trying to understand how to do it. Just ideas please.

Edited 5 Years Ago by Crutoy: n/a

I'd say the spec is wrong:

int move_disk(int disk,int peg1,int peg2,int peg3)

I think it's this:

// return true if move was allowed, false otherwise
bool move_disk(int fromPegNum, int toPegNum)

Presumably you have arrays

int peg1[5];
int peg2[5];
int peg3[5];

make -1 represent "no disk"

If you have 5 disks, they'll be numbered 1 through 5. 5 is the biggest, 1 is the smallest.

If peg 1 has disks 2 and 5 on it and peg 2 has disks 1 and 4 on it and peg3 has disk 3 on

peg1 would be {2,5,-1,-1,-1}
peg2 would be {1, 4, -1, -1, -1}
peg3 would be {3, -1, -1, -1, -1}

move(1,3) would return true and the arrays end up:

peg1 would be {5,-1,-1,-1}
peg2 would be {1, 4, -1, -1, -1}
peg3 would be {2,3, -1, -1, -1}

move(3,1) would return false because disk 3 can't be placed on top of disk 2.

That's how I've always done it, at least.

i should have been more clearer in my post. This function prototype is given by the book , so i have to use it, also no arrays are not allowed to be used with this program.

Problem is im lost because the way the function is defined i have integer disks that defines how many disks are there. Peg1 defines that disks are threaded on that initial peg.So if i have 3 disks and i move one disk to peg3 i would subtract from disks and from peg1 and add a disk to peg3. If i move a disk from peg1 to peg2 again i subtract from disks and add to peg2. Now this is where its confusing. Since peg2 have to have disk #2 as a value but it only has value of 1, and what happens if i now want to move disk from peg1 to peg2 i shouldnt be allowed. I can't find the logic how to represent disks in terms of actual disk value

Do some more searching here @ DaniWeb. I know there are other threads somewhere with a similar formula.

If I remember correctly, arg1 is the disc's ID number being moved (not remaining disc count) with args 2-4 being the ID number of the top disc on the respective peg...

Edited 5 Years Ago by Fbody: n/a

If that's the case what happens to id's once i move one disk on top of another ? How can i store two id's for one peg. Its a bit frustrating.

If that's the case what happens to id's once i move one disk on top of another ? How can i store two id's for one peg. Its a bit frustrating.

Like I said, if I remember correctly. I know that a recursive version of the puzzle with that same prototype has been discussed before. Start searching.

I can't search , i don't want to come up on the solution, Thanks though.

I can't search , i don't want to come up on the solution, Thanks though.

????

So read the descriptions and ignore the code then.


Next time, put all this info in the first post. There's more than one way to do it and more than one way to define "it"(i.e. what you're doing). If you were given the prototype, they should have given you some description of what each parameter meant and how data is stored.

Ok, point taken i'll post the whole requirement of a problem.
Moving n disks can be viewed in terms of moving only n - 1 disks as follows:
A)Move n - 1 disks from peg 1 to peg 2 using peg 3 as a temporary holding area.
B)Move the last disk(the largest) from peg1 to peg 3
C)Move the n - 1 disks from peg 2 to peg 3 using peg 1 as a temporary holding area.
The process ends when the last task involves moving n = 1 disks the base case this accomplished by moving the disk without the need to move it to temporary holding area. Use a recursive function with four parameters.
a)Number of disks to be moved
b)the peg on which these disks are initially threaded
c)the peg to which this stack of disks is to be moved
d)the peg to be used as a temporary holding area.
moves should be printed as
1 --> 3
1 --> 2
3 --> 2
1 --> 3
2 --> 1
2 --> 3
1 --> 3
I dont understand how to keep track of disks once they are moved from one column to another , i loose the value of initial disk.

I dont understand how to keep track of disks once they are moved from one column to another , i loose the value of initial disk.

You don't keep track of any values of any disk. There are no values anywhere here. If you are moving 4 disks from one peg to another, you don't know or care which 4 disks they are. You care about how many disks are on a peg, not which disks they are, at least with this method.

But then im gonna lose the the sizes it might mean that larger disk can be placed on the smaller. With that logic i can't know which disk is larger all i know is it has a disk on peg. I must be stupid i just don't see it.

But then im gonna lose the the sizes it might mean that larger disk can be placed on the smaller. With that logic i can't know which disk is larger all i know is it has a disk on peg. I must be stupid i just don't see it.

Here's the deal. It's a "trusting" function. It trusts you enough to know that you'd never do anything dastardly like make an illegal move like that. And if you stick with the Tower of Hanoi solution algorithm, you never will.

The code is pretty short. Hell it's only a few lines. To get 7 pegs from peg 1 to peg 2:

  1. Move 6 pegs from peg 1 to peg 3.
    1. Move 5 pegs from peg 1 to peg 2.
      1. Move 4 pegs from peg 1 to peg 3.
        1. Move 3 pegs from peg 1 to peg 2.
          1. Move 2 pegs from peg 1 to peg 3.
            1. Move 1 peg from peg 1 to peg 2.
            2. Move 1 peg from peg 1 to peg 3.
            3. Move 1 peg from peg 2 to peg 3.
          2. Move 1 peg from peg 1 to peg 2.
          3. Move 2 pegs from peg 3 to peg 2.
        2. Move 1 peg from peg 1 to peg 3.
        3. Move 3 pegs from peg 3 to peg 3.
      2. Move 1 peg from peg 1 to peg 2.
      3. Move 4 pegs from peg 3 to peg 2.
    2. Move 1 peg from peg 1 to peg 3.
    3. Move 5 pegs from peg 2 to peg 3.
  2. Move 1 peg from peg 1 to peg 2.
  3. Move 6 pegs from peg 3 to peg 2.

Change the word "peg" to "disk" before the words "from". I don't have time to edit. I also imagine that I screwed up on the copy/paste a few times, but there's your strategy. Each step is a call. Look at the numbers and turn them into parameters.

But then im gonna lose the the sizes it might mean that larger disk can be placed on the smaller. With that logic i can't know which disk is larger all i know is it has a disk on peg. I must be stupid i just don't see it.

No, you're not stupid. The problem as you understand it is.
You have 3 cans in front of you. None have labels. Hand me the creamed corn.
This is the definition of the problem as you've laid it out.

Reread the problem again. Where in the problem does it say arrays cannot be used? You must keep track of what specific disks are on a peg. Without that information you cannot proceed as you have discovered. So each peg needs to be an array.

Edited 5 Years Ago by WaltP: n/a

Reason why i say arrays are not allowed is because they haven't been covered up to this exercise, They will be covered in the next chapter. It drives me mad, cause i can't move on through the book unless i solve the exercise.

The problem as you understand it is.
You have 3 cans in front of you. None have labels. Hand me the creamed corn.
This is the definition of the problem as you've laid it out.

You must keep track of what specific disks are on a peg. Without that information you cannot proceed as you have discovered. So each peg needs to be an array.

If the problem was indeed "Hand me the creamed corn", they'd need labels and he'd need to keep track of what disks were on what pegs and there would be arrays, stacks, whatever, involved.

But if the problem is simply to print out the steps needed for someone to solve the Tower of Hanoi, as the printout suggests:

1 --> 3
1 --> 2
3 --> 2
1 --> 3
2 --> 1
2 --> 3
1 --> 3

keeping track of what disk is where is unnecessary. Note that at no time are you required in the printout to be display the actual pegs and their contents.

This is what i understand from the instructions. My initial call have to be such as

move_disk(3,1,3,2)

am i correct so far, parameter values correspond to the problems requirements i think. First is number of disks to be moved, second is what peg they are threaded , third is where to move the disk, 4th is temp storage. So far so good ? If i dont check for the sizes how can i know what move is next without checking the size of the disk on the peg ? It don't make sense to me.

Edited 5 Years Ago by Crutoy: n/a

Sounds like a question for the teacher. I feel certain he has the answers that we seem to be missing.

Im self studying from the book , just trying to learn the language, So im heavily relying on the message boards for guidance. Thanks to everyone for taking their time on this. I might have to skip this one and come back to it sometime later.

>>If i dont check for the sizes how can i know what move is next without checking the size of the disk on the peg ?

Read my earlier post with the nested steps. I did a lot of copy and pasting. I'm sure I screwed up a few times with it. Below, however, is right.

To move 7 disks from 1 to 3: (missing parameter is the other peg, 2)
1. Move 6 disks from peg 1 to peg 2.(missing parameter is the other peg, 3)
2. Move 1 disks from peg 1 to peg 3.(missing parameter is the other peg, 2)
3. Move 6 disks from peg 2 to peg 3(missing parameter is the other peg, 1)

Red = number of disks to move. I couldn't care less how many disks are on the pegs. It's irrelevant. If I'm moving 7 disks, I am moving the TOP 7 disks. I couldn't care less how many disks are underneath. I couldn't care less how many disks are on the other pegs. I couldn't care less what the sizes of the disks I am moving are. Put the C++ code away. Do it on paper till you get the system down. Write down the process in explicit detail to the point where you could explain it to someone who has never done it. Then turn it into code. See my earlier nested list.

Edited 5 Years Ago by VernonDozier: n/a

I went over it a dozen times on paper, its simple algorithm but if you don't take the size into equation it don't make sense to me.

I went over it a dozen times on paper, its simple algorithm but if you don't take the size into equation it don't make sense to me.

Then I suggest throwing the instructions out and writing it in a way that makes sense to you, getting it to work, and it least you'll have a sense of accomplishment.

I can't explain it any better without giving you the code, which you said you didn't want. Do you want it?

No thank you , again thanks for the patients. I'll keep trying to work on it.

This article has been dead for over six months. Start a new discussion instead.