My assignment is to solve the Towers of Hanoi for any number using recursion. I wrote my code in C++.
Rules:
- Cannot stack a larger disk on top of a smaller disk.
- Cannot move more than one disk at a time.
** 3. Only move a disk one peg at a time without going back to the start or going out of the end. <- This is what i'm currently struggling with. **
Following: START --> peg1 <--> peg2 <--> peg3 --> END
#include <iostream>
#include <time.h>
using namespace std;
void move(int, int, int, int, int, int);
int i, j, l, n;
const int start = 1, end = 5, aux1 = 2, aux2 = 3, aux3 = 4;
int main(){
double time = 0;
clock_t begin, stop;
begin = clock();
for(n = 10; n>=1; n--){
l = 0, i = 0, j = 0;
move(n, start, end, aux1, aux2, aux3);
cout << "Number of disks moved: " << n << endl;
cout << "Number of moves made: " << l << endl;
}
stop = clock();
time = (stop - begin)/1000.00;
cout << "Game solved in: " << time << " miliseconds";
return 0;
}
void move(int n, int start, int end, int aux1, int aux2, int aux3){
if(n>0){
l++;
if(i>=100){
j++;
if(l - j == i){
move(n-1, start, aux1, aux2, aux3, end);
cout << "Move disc " << n << " from peg " << start << " to peg " << end << endl;
move(n-1, aux1, aux2, aux3, end, start);
}
}
if(i<=100){
i++;
move(n-1, start, aux1, aux2, aux3, end);
cout << "Move disc " << n << " from peg " << start << " to peg " << end << endl;
move(n-1, aux1, end, aux3, aux2, start);
}
}
}
Example for 3 Disks, the code puts
Move disc 1 from peg 1 to peg 3
Move disc 2 from peg 1 to peg 2
Move disc 1 from peg 3 to peg 2
Move disc 3 from peg 1 to peg 5
Move disc 1 from peg 2 to peg 4
Move disc 2 from peg 2 to peg 5
Move disc 1 from peg 4 to peg 5
Number of disks moved: 3
Number of moves made: 7
Example of what I need the algorithm to put for 3 Disks:
Move disc 1 from peg 1 to peg 2
Move disc 1 from peg 2 to peg 3
Move disc 1 from peg 3 to peg 4
Move disc 2 from peg 1 to peg 2
Move disc 2 from peg 2 to peg 3
Move disc 1 from peg 4 to peg 3
Move disc 1 from peg 3 to peg 2
Move disc 2 from peg 3 to peg 4
Move disc 1 from peg 2 to peg 3
Move disc 1 from peg 3 to peg 4
Move disc 3 from peg 1 to peg 2
Move disc 3 from peg 2 to peg 3
Move disc 1 from peg 4 to peg 3
Move disc 1 from peg 3 to peg 2
Move disc 2 from peg 4 to peg 3
Move disc 1 from peg 2 to peg 3
Move disc 1 from peg 3 to peg 4
Move disc 2 from peg 3 to peg 2
Move disc 1 from peg 4 to peg 3
Move disc 1 from peg 3 to peg 2
Move disc 3 from peg 3 to peg 4
Move disc 3 from peg 4 to peg 5
Move disc 1 from peg 2 to peg 3
Move disc 1 from peg 3 to peg 4
Move disc 2 from peg 2 to peg 3
Move disc 1 from peg 4 to peg 3
Move disc 1 from peg 3 to peg 2
Move disc 2 from peg 3 to peg 4
Move disc 2 from peg 4 to peg 5
Move disc 1 from peg 2 to peg 3
Move disc 1 from peg 3 to peg 4
Move disc 1 from peg 4 to peg 5
Number of disks moved: 3
Number of moves made: 32
I am so lost, I have no idea how to make the code not let the disk skip a peg. It's probably staring me right in the face but i cannot for the life of me figure it out.
Please ignore the for loops 'i' and 'j', those were made so that if the results get too big, it will print the first 100 moves and the last 100 moves.
Thank you!