Hanoi Towers with user input

[kabilah]

I'm having an issue with a Hanoi Tower problem. I'm passing an index variable and a vector to the recursive function. The disc numbers are being displayed correctly, but the peg numbers are not. The output is only the moves not the disc numbers on each peg.

Output should be Disc number 1 moved from peg 1 to peg 3. For the first move in a three peg and three disc run through. I've written a static version before, but the user defined variability is kinda throwing me through a loop.

My question is am I on the right track, and if so how can I get around the brick wall I keep running into? And yes, I may be at least somewhat retarded. :)

#include <iostream>
#include <vector>

using namespace std;

void moveDiscs(int, int, vector<int>);

int main()
{
	int numDiscs;
	int numPegs;
	int index = 0;

	//user input
	cout << "Enter the number of discs to use: " << endl;
	cin >> numDiscs;

	cout << "Enter the number of pegs to use: " << endl;
	cin >> numPegs;

	//vector to hold peg information
	vector<int> Pegs(numPegs);
	
	//populate vector
	Pegs[0] = numDiscs;

	for(int i = 1; i <Pegs.size(); i++)
	{
		Pegs[i] = 0;
	}

	moveDiscs(numDiscs, index, Pegs);

	cout << "All the discs are moved." << endl;

	system("PAUSE");
	return 0;
}

void moveDiscs(int num, int index, vector<int> pegs)
{
	if(num > 0)
	{
		
		moveDiscs(num-1, index, pegs);
		if(index < pegs.size())
			++index;
		if(index == pegs.size())
			index = 0;
		
		
		cout << "Move ring " << num << " from peg " << index
			<< " to peg " << index + 1 << endl;
		
		index++;
		if(index == pegs.size())
			index = 0;
		
		
		moveDiscs(num-1, index, pegs);
	}
}

[VernonDozier]

I don't think it has anything to do with user input. The algorithm itself is flawed, recursion or no recursion. It immediately flunks for a non-recursive example. One disk, three pegs. One move from either peg 0 to peg 2 or peg 1 to peg 3, depending on how you're defining it. The point is that it should skip a peg. Your printout only allows for adjacent peg moves on lines 52 and 53, so right off the bat, you don't have to look at anything other than those two lines to see there's a problem. Efficient Tower of Hanoi algorithms need to allow for moves between non-adjacent pegs. I'll also point out that I see no attempt to adjust pegs in moveDiscs, so what's the point of that variable? You check the size and that's it. If all you care about is the size, there's no point having the vector.

[kabilah]

Wow I was more tired than I thought. Sorry to have wasted the viewers time so far.

I must have posted after I'd deleted the functionality in moveDiscs. I'll work on it and repost the function.

[kabilah]

void moveDiscs(int num, int index, vector<int> pegs, int destination)
{
	if(num > 0)
	{
		moveDiscs(num-1, index, pegs, destination);
		pegs[destination]++;
		pegs[index]--;
		
		cout << "Move ring " << num << " from peg " << index+1
			<< " to peg " << destination+1 << endl;
		destination--;

		moveDiscs(num-1, destination, pegs, index);
	}
}

[VernonDozier]

You'll have to post the whole program since the function definition changed. What precisely does the pegs vector represent and what precisely is the moveDiscs function supposed to do?

[kabilah]

I used the Pegs vector to signify the number of pegs. moveDiscs is supposed to move the discs between the locations of the pegs vector and increment and decrement each location of the vector as needed.

#include <iostream>
#include <vector>

using namespace std;

void moveDiscs(int, int, vector<int>, int);

int main()
{
	int numDiscs;
	int numPegs;
	int index = 0;
	int destinationPeg; //final position of the vector

	//user input
	cout << "Enter the number of discs to use: " << endl;
	cin >> numDiscs;

	cout << "Enter the number of pegs to use: " << endl;
	cin >> numPegs;

	//vector to hold peg information
	vector<int> Pegs(numPegs);
	
	//populate vector
	Pegs[0] = numDiscs;

	for(int i = 1; i <Pegs.size(); i++)
	{
		Pegs[i] = 0;
	}

	destinationPeg = (Pegs.size() - 1);

	moveDiscs(numDiscs, index, Pegs, destinationPeg);

	cout << "All the discs are moved." << endl;

	system("PAUSE");
	return 0;
}

void moveDiscs(int num, int index, vector<int> pegs, int destination)
{
	if(num > 0)
	{
		moveDiscs(num-1, index, pegs, destination);
		pegs[destination]++;
		pegs[index]--;
		
		cout << "Move ring " << num << " from peg " << index+1
			<< " to peg " << destination+1 << endl;
				
		destination--;

		moveDiscs(num-1, destination, pegs, index);
	}
}

[VernonDozier]

>> I used the Pegs vector to signify the number of pegs.

You do not. You are using the Pegs vector to signify the number of rings on each peg.

Since the peg vector only keeps track of HOW MANY rings are on a peg, but does not keep track of WHICH rings are on a peg, I'm thinking there's no sense displaying a "ring number" when you move a ring from peg to peg, so I'm wondering if you should possibly change lines 51 and 52 to this...

cout << "Move top ring of peg " << index+1
			<< " to peg " << destination+1 << endl;

You also adjust the pegs vector but make no use of it in the function, so what's the point of having it?

You're also not checking values to make sure they are valid. That's why your program crashes. See the revisions I've made. This doesn't fix anything, but it shows you where you are getting your run-time errors and why.

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

void moveDiscs(int, int, vector<int>, int);

int main()
{
	int numDiscs;
	int numPegs;
	int index = 0;
	int destinationPeg; //final position of the vector

	//user input
	cout << "Enter the number of discs to use: " << endl;
	cin >> numDiscs;

	cout << "Enter the number of pegs to use: " << endl;
	cin >> numPegs;

	//vector to hold peg information
	vector<int> Pegs(numPegs);
	
	//populate vector
	Pegs[0] = numDiscs;

	for(int i = 1; i <Pegs.size(); i++)
	{
		Pegs[i] = 0;
	}

	destinationPeg = (Pegs.size() - 1);

	moveDiscs(numDiscs, index, Pegs, destinationPeg);

	cout << "All the discs are moved." << endl;

	system("PAUSE");
	return 0;
}

void moveDiscs(int num, int index, vector<int> pegs, int destination)
{
    assert(pegs.size() >= 2);
    assert(num >= 0);
    assert(index >= 0);
    assert(index < pegs.size());
    assert(destination >= 0);
    assert(destination < pegs.size());
    for(int i = 0; i < pegs.size(); i++)
    {
        assert(pegs[i] >= 0);
    }
    
	if(num > 0)
	{
		moveDiscs(num-1, index, pegs, destination);
		pegs[destination]++;
		pegs[index]--;
		
		cout << "Move ring " << num << " from peg " << index+1
			<< " to peg " << destination+1 << endl;
				
		destination--;

		moveDiscs(num-1, destination, pegs, index);
	}
}

[kabilah]

>> I used the Pegs vector to signify the number of pegs.

You do not. You are using the Pegs vector to signify the number of rings on each peg.

That's the value in each point on the vector, not the vector itself. Each location within the vector is a peg.

Since the peg vector only keeps track of HOW MANY rings are on a peg, but does not keep track of WHICH rings are on a peg, I'm thinking there's no sense displaying a "ring number" when you move a ring from peg to peg, so I'm wondering if you should possibly change lines 51 and 52 to this...

cout << "Move top ring of peg " << index+1
			<< " to peg " << destination+1 << endl;

The only reason I put that is because I'm running another Hanoi Towers program with static 3 rings and 3 pegs. I use it for output testing only and I don't plan on having it in the final version.

You also adjust the pegs vector but make no use of it in the function, so what's the point of having it?

I didn't want to use a dynamic array and chose to use a vector instead. I needed to accommodate user input on not only the number of pegs but also the number of rings.

You're also not checking values to make sure they are valid. That's why your program crashes. See the revisions I've made. This doesn't fix anything, but it shows you where you are getting your run-time errors and why.

I am concerned with the recursive algorithm running right now and was planning on implementing input validation after that works.

[kabilah]

The base case of one ring and any number of pegs works.

Now with two rings and 3 pegs, I'm having the problem of a duplicated move from peg 1 to peg 2.

void moveDiscs(int num, int index, vector<int> pegs, int destination)
{
	if(num > 0 && (num % 2) == 0)
	{
		destination--;

		moveDiscs(num-1, index, pegs, destination);
		pegs[destination]++;
		pegs[index]--;
		cout << "Move top ring from peg " << index+1
			<< " to peg " << destination+1 << endl; 
		
		destination++;;
		moveDiscs(num-1, index, pegs, destination);

	}

	if(num > 0 && (num % 2) == 1)
	{
		moveDiscs(num-1, index, pegs, destination);
		pegs[destination]++;
		pegs[index]--;
		
		cout << "Move top ring from peg " << index+1
			<< " to peg " << destination+1 << endl;
				
		
		moveDiscs(num-1, index, pegs, destination);
		
	}
}

[VernonDozier]

You're missing the point. The issue is not the user input or validation of the user input, allocation of the vector, whether to use a vector or a dynamic array, etc. All that's fine, or even if not fine, it's not the problem you're bumping into right now. It's the rest of it.

I re-iterate my point in my prior post. And this point has nothing to do with the size of the pegs vector nor the fact that it's a vector, not an array. You do not use the pegs vector to make any decisions on how/whether to move. Therefore why is it there and why bother adjusting it at all? The only purpose it currently serves is to potentially give you a seg fault.

[kabilah]

I'm not doing anything with the numbers at this point because they don't really have any effect. I was planning on expanding the project to use other objects (hence vectors), but I need the algorithm to work first.

[kabilah]

I take your meaning now that it's been restated. I apologize for not understanding when it was first said. And I do appreciate the help.

I've gone back to my original program and modified it to take input for only pegs. There are only 5 rings to deal with as per the assignment and a user defined number of pegs.

I, as I have previously shown, have no idea how to implement user defined pegs. I've been working on this since monday afternoon.

Here's what I have:

#include <iostream>

using namespace std;

void moveDiscs(int, int, int, int, int);

int main()
{
	int numRings = 5;
	int numPegs;
	
	cout << "Enter the number of pegs." << endl;
	cin >> numPegs;
	
	int fromPeg = 1;
	int toPeg = 3;
	int tempPeg = 2;
	
	moveDiscs(numRings, fromPeg, toPeg, tempPeg, numPegs);

	cout << "All the pegs are moved!\n";
	
	system("PAUSE");
	return 0;
}

void moveDiscs(int num, int fromPeg, int toPeg, int tempPeg, int numPegs)
{
	if(num > 0)
	{
		moveDiscs(num - 1, fromPeg, tempPeg, toPeg, numPegs);
		
		cout << "Move top disc from peg " << fromPeg 
			<< " to peg " << toPeg << endl;
				
		moveDiscs(num - 1, tempPeg, toPeg, fromPeg, numPegs);

                //I know I need to shift which pegs are active
		//not sure of the method
		fromPeg++;
		toPeg++;
		tempPeg++;
		if(fromPeg == (numPegs + 1))
			fromPeg = 1;
		if(toPeg == (numPegs + 1))
			toPeg = 1;
		if(tempPeg == (numPegs + 1))
			tempPeg = 1;
	}
}

[kabilah]

I, as I have previously shown, have no idea how to implement user defined pegs.

I can manually program 4 pegs or 5 or even 6 by adding more and more intermediate pegs and continuously shifting them through the algorithm. What I need help with is a solution for K pegs, where K is a user defined number up to the maximum of a long int. This may be asking too much, because I can code variations of moveDisc for instances of 1 peg to 10 pegs. I didn't do that to start because I know it can be done, but I don't know how to do it without K number of functions.

[VernonDozier]

Setting up the algorithm using N rings and 4 pegs using the FEWEST number of moves possible is significantly more difficult than doing it with N rings and 3 pegs. Why? Because you have more than one option that will eventually work using 4 pegs and you have to decide which works the best. Add enough rings and it's impossible. From Wikipedia...

http://en.wikipedia.org/wiki/Tower_of_Hanoi#Four_pegs_and_beyond

Although the three-peg version has a simple recursive solution as outlined above, the optimal solution for the Tower of Hanoi problem with four pegs (called Reve's puzzle), let alone more pegs, is still an open problem. This is a good example of how a simple, solvable problem can be made dramatically more difficult by slightly loosening one of the problem constraints.
The fact that the problem with four or more pegs is an open problem does not imply that no algorithm exists for finding (all of) the optimal solutions. Simply represent the game by an undirected graph, the nodes being distributions of disks and the edges being moves and use breadth first search to find one (or all) shortest paths moving a tower from one peg onto another one. However, even smartly implemented on the fastest computer now available, this algorithm provides no way of effectively computing solutions for large numbers of disks; the program would require more time and memory than available. Hence, even having an algorithm, it remains unknown how many moves an optimal solution requires and how many optimal solutions exist for 1000 disks and 10 pegs.

With 3 pegs there is only one move that will ever work at all for any given situation.

I'm seeing a word that piqued my curiosity that you perhaps do not have the correct algorithm: "shifting". You may indeed have the algorithm down and cannot implement it or you might have the wrong algorithm. I cannot tell.

My advice is to write a program that takes 3 pegs and N disks, get it to work, then write one that takes 4 pegs and N disks and get that to work. Forget about user-defined number of pegs at the moment. When you have those down, go back.

>> There are only 5 rings to deal with as per the assignment and a user defined number of pegs.

This strikes me as odd. If you have 5 disks and, say, 12 pegs, you make life easy and just ignore 7 of them completely. It will take 9 moves. Again, this piques my curiosity pertaining to the word "shifting" and the algorithm.

This is also a pencil and paper exercise. Get the algorithm down first before you try to code.

[TrustyTony]

Are you using the Frame-Stewart algorighm?

[kabilah]

Are you using the Frame-Stewart algorighm?

Yeah, read it a couple times before I came here for help. It tells me the number of moves beautifully, but translating that into a useful C++ algorithm that will display the moves is something I'm not doing well.

[kabilah]

Setting up the algorithm using N rings and 4 pegs using the FEWEST number of moves possible is significantly more difficult than doing it with N rings and 3 pegs. Why? Because you have more than one option that will eventually work using 4 pegs and you have to decide which works the best. Add enough rings and it's impossible. From Wikipedia...

http://en.wikipedia.org/wiki/Tower_of_Hanoi#Four_pegs_and_beyond

With 3 pegs there is only one move that will ever work at all for any given situation.

I'm seeing a word that piqued my curiosity that you perhaps do not have the correct algorithm: "shifting". You may indeed have the algorithm down and cannot implement it or you might have the wrong algorithm. I cannot tell.

My advice is to write a program that takes 3 pegs and N disks, get it to work, then write one that takes 4 pegs and N disks and get that to work. Forget about user-defined number of pegs at the moment. When you have those down, go back.

>> There are only 5 rings to deal with as per the assignment and a user defined number of pegs.

This strikes me as odd. If you have 5 disks and, say, 12 pegs, you make life easy and just ignore 7 of them completely. It will take 9 moves. Again, this piques my curiosity pertaining to the word "shifting" and the algorithm.

This is also a pencil and paper exercise. Get the algorithm down first before you try to code.

I may have used the wrong word when I said shifting. The base algorithm (n < 20 rings and 3 pegs) works by switching the variables in the recursive function call allowing for the change in destination, temp, and from locations.

[kabilah]

I really appreciate the help, but the assignment had a typo. The word peg was put in when ring was supposed to be used. I really do appreciate the help, thank you. I will continue to work on the peg problem.