C++

Forum

 
Towers of Hanoi - 5 peg, 1-10 disks

Metal488 (19)
So I an working on a program to solve the Towers of Hanoi puzzle with an extra rule. The disks must follow a graph with edges: (start, a1), (a1,a2), (a2,a3), (a3,a1), (a3,dest).

Pegs: start, a1, a2, a3, dest
Disks: I have to solve it for n disks = (1,2,3,4,5,6,7,8,9,10)

So there is a cycle that I know is the key to solving this. I know to solve this, I need to move n-1 disks to a3, then move the last disk to a2, then move n-1 disks to a1, then the last disk to dest, then n-1 to dest, but I am having major trouble actually implementing this.

This is what I currently have:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
#include <iostream>

using namespace std;

void Hanoi2(string, string, string, string, int, bool);

void Hanoi1(string start, string dest, string a2, string a3, int n)
{
	if(n==1)
	{
		cout << "Move disk " << n << " from " << start << " to " << dest << endl;
	}
	else
	{
		Hanoi2(start, dest, a2, a3, n-1, false);
		cout << "Move disk " << n << " from " << start << " to " << dest << endl;
		Hanoi1(a3, start, dest, a2, n-1);
		Hanoi1(start, dest, a2, a3, n-1);
	}
}

void Hanoi2(string start, string a2, string a3, string dest, int  n, bool isFlagged)
{
	if(n==1)
	{
//		if(isFlagged == true)
//			start = "start";
//		cout << "Move disk " << n << " from " << start << " to " << dest << endl;
		if(isFlagged == 1)
			cout << "Move disk " << n << " from start to " << dest << endl;
		else
			cout << "Move disk " << n << " from " << start << " to " << dest << endl;
	}
	else
	{
		Hanoi2(start, a2, a3, dest, n-1, isFlagged);
//		if(isFlagged == true)
//			start = "start";
//		cout << "Move disk " << n << " from " << start << " to " << a3 << endl;
		if(isFlagged == 1)
			cout << "Move disk " << n << " from start to " << a3 << endl;
		else
			cout << "Move disk " << n << " from " << start << " to " << a3 << endl;
		Hanoi1(dest, start, a2, a3, n-1);
		cout << "Move disk " << n << " from " << a3 << " to " << dest << endl;
		Hanoi2(start, a2, a3, dest, n-1, false);
	}
}

void Hanoi3(string start, string a1, string a2, string a3, string dest, int n, bool isFlagged)
{
	if(n==1)
	{
		cout << "Move disk " << n << " from " << start << " to " << dest << endl;
	}
	else
	{
		Hanoi2(a1, a1, a2, a3, n-1, isFlagged);
		cout << "Move disk " << n << " from start to a1" << endl;
		cout << "Move disk " << n << " from a1 to a2" << endl;
		Hanoi1(a3,a1,a1,a2, n-1);
		cout << "Move disk " << n << " from a3 to dest" << endl;
		Hanoi3(a1,a2,a2,a3,dest,n-1,false);
	}
}

int main()
{
	Hanoi3("start", "a1", "a2", "a3", "dest", 3, true);

	return 0;
}


This is what I get for 3 disks:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
Move disk 1 from start to a3
Move disk 2 from start to a2
Move disk 1 from a3 to a1
Move disk 2 from a2 to a3
Move disk 1 from a1 to a3
Move disk 3 from start to a1
Move disk 3 from a1 to a2
Move disk 1 from a3 to a2
Move disk 2 from a3 to a1
Move disk 1 from a2 to a3
Move disk 1 from a3 to a1
Move disk 3 from a3 to dest
Move disk 1 from a2 to a3
Move disk 2 from start to a1
Move disk 2 from a1 to a2
Move disk 1 from a3 to a2
Move disk 2 from a3 to dest
Move disk 1 from a2 to dest


I need to change the code so that it prints each individual move (instead of saying a3 to a1 for example), but first I'm trying to get it to properly follow the graph.

The issues with the output above includes:
Move disk 1 from a3 to a1
Move disk 1 from a2 to a3
For these 2 moves, disk 1 is coming from a1, not a2

Move disk 2 from start to a1
Move disk 2 from a1 to a2
For some reason it tries to bring disk 2 from start again even though it is at a1, not start.

Move disk 2 from a3 to dest
Then it says this when disk 2 is at a1.

These are the obvious issues I see, but I'm not sure how to fix them at all.

Any help would be greatly appreciated. I've been trying to figure out this puzzle for days now with little to no luck.

Last edited on
Metal488 (19)
I changed line 63 to
Hanoi3(a1,a1,a2,a3,dest,n-1,false);
and added an if statement around lines 59 and 60:
1
2
3
4
5
 
if(isFlagged == 1)
{
	cout << "3b) Move disk " << n << " from start to a1" << endl;
	cout << "3c) Move disk " << n << " from a1 to a2" << endl;
}

(the 3b and 3c are just something I added to tell me where the mistakes were coming from)

with these adjustments, I now get this for my output:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
2a) Move disk 1 from start to a3
2c) Move disk 2 from start to a2
1a) Move disk 1 from a3 to a1
2e) Move disk 2 from a2 to a3
2b) Move disk 1 from a1 to a3
3b) Move disk 3 from start to a1
3c) Move disk 3 from a1 to a2
2b) Move disk 1 from a3 to a2
1b) Move disk 2 from a3 to a1
1a) Move disk 1 from a2 to a3
1a) Move disk 1 from a3 to a1
3d) Move disk 3 from a3 to dest
2b) Move disk 1 from a1 to a3
1a) Move disk 1 from a3 to a1
3d) Move disk 2 from a3 to dest
3a) Move disk 1 from a1 to dest


(the number at the beginning of the line is which hanoi function it's in (Hanoi1, Hanoi2, Hanoi3) and the letter marks which cout statement it is in that function (a = 1st, b = 2nd,...)

Now the problem's are:
2nd to last line says a3 to dest, but disk 2 was at a1
line 12 of output says disk 3 from a3 to dest, but disk 3 was at a2
There also appears to be something wrong with the last 4 moves because disks 1 and 2 end up on a1, then it tries to move disk 2 to dest, but that's wrong because it is under disk1.

Topic archived. No new replies allowed.