CSCI 261 - Programming Concepts - Maynooth 2022

Lab 5A - Recursion I: Towers of Hanoi

This lab is due by Friday, July 22, 2022 11:59 PM.
As with all labs you may, and are encouraged, to pair program a solution to this lab. If you choose to pair program a solution, be sure that you individually understand how to generate the correct solution.

Begin by reviewing the recursive solution to this task. Once you feel comfortable with the process, return to the lab. A starting solution has been provided for you. Your job is to complete this implementation so that the function is called recursively properly and solves the Towers of Hanoi task. 

#include <iostream>
using namespace std;

/**
 * @brief Recursive solution to move N disks from a starting peg to a target peg
 *
 * @param N the number of disks to move
 * @param START_PEG ID of the peg the disks are currently on
 * @param TARGET_PEG ID of the peg the disks need to move to
 * @param SPARE_PEG ID of the peg that can be used as temporary storage
 *
 * @note Outputs the series of moves to standard otu to solve the problem for N disks
 */
void towers_of_hanoi(const int N, const int START_PEG, const int TARGET_PEG, const int SPARE_PEG) {
    // base case - if there are no more disks to move, then we are done!  do nothing


    // recursive case
    // Step 1: recursively move the top N-1 disks from our current peg
    // to the non-target peg


    // Step 2: move the largest disk that was on the bottom from our
    // current peg to the target peg
    // (perform the move by printing what disk moves from where to where)
    cout << "Move disk " << N << " from " << " to " << endl;

    // Step 3: recursively move the remaining N-1 disks from the non-target
    // peg to our target peg on top of the largest disk we just moved

}

int main() {
    const int STARTING_PEG = 0;         // 0 - ID of the peg our disks start on
    const int TARGET_PEG = 2;           // 2 - ID of the peg we need to move our disks to
    const int SPARE_PEG = 1;            // 1 - ID of the peg that can be used for temp storage

    int numberOfDisks;
    cout << "Enter number of disks to solve: ";
    cin >> numberOfDisks;               // user enters the number of disks to solve for

    // solve Towers of Hanoi problem for numberOfDisks disks
    // disks are initially on our starting peg and need to move to our target peg
    towers_of_hanoi( numberOfDisks, STARTING_PEG, TARGET_PEG, SPARE_PEG );

    return 0;
}

Sample Runs

Below are several expected outputs of the program running: 

Enter number of disks to solve: 1
Move disk 1 from 0 to 2
Enter number of disks to solve: 3
Move disk 1 from 0 to 2
Move disk 2 from 0 to 1
Move disk 1 from 2 to 1
Move disk 3 from 0 to 2
Move disk 1 from 1 to 0
Move disk 2 from 1 to 2
Move disk 1 from 0 to 2
Enter number of disks to solve: 4
Move disk 1 from 0 to 1
Move disk 2 from 0 to 2
Move disk 1 from 1 to 2
Move disk 3 from 0 to 1
Move disk 1 from 2 to 0
Move disk 2 from 2 to 1
Move disk 1 from 0 to 1
Move disk 4 from 0 to 2
Move disk 1 from 1 to 2
Move disk 2 from 1 to 0
Move disk 1 from 2 to 0
Move disk 3 from 1 to 2
Move disk 1 from 0 to 1
Move disk 2 from 0 to 2
Move disk 1 from 1 to 2
Enter number of disks to solve: 7
Move disk 1 from 0 to 2
Move disk 2 from 0 to 1
Move disk 1 from 2 to 1
Move disk 3 from 0 to 2
Move disk 1 from 1 to 0
Move disk 2 from 1 to 2
Move disk 1 from 0 to 2
Move disk 4 from 0 to 1
Move disk 1 from 2 to 1
Move disk 2 from 2 to 0
Move disk 1 from 1 to 0
Move disk 3 from 2 to 1
Move disk 1 from 0 to 2
Move disk 2 from 0 to 1
Move disk 1 from 2 to 1
Move disk 5 from 0 to 2
Move disk 1 from 1 to 0
Move disk 2 from 1 to 2
Move disk 1 from 0 to 2
Move disk 3 from 1 to 0
Move disk 1 from 2 to 1
Move disk 2 from 2 to 0
Move disk 1 from 1 to 0
Move disk 4 from 1 to 2
Move disk 1 from 0 to 2
Move disk 2 from 0 to 1
Move disk 1 from 2 to 1
Move disk 3 from 0 to 2
Move disk 1 from 1 to 0
Move disk 2 from 1 to 2
Move disk 1 from 0 to 2
Move disk 6 from 0 to 1
Move disk 1 from 2 to 1
Move disk 2 from 2 to 0
Move disk 1 from 1 to 0
Move disk 3 from 2 to 1
Move disk 1 from 0 to 2
Move disk 2 from 0 to 1
Move disk 1 from 2 to 1
Move disk 4 from 2 to 0
Move disk 1 from 1 to 0
Move disk 2 from 1 to 2
Move disk 1 from 0 to 2
Move disk 3 from 1 to 0
Move disk 1 from 2 to 1
Move disk 2 from 2 to 0
Move disk 1 from 1 to 0
Move disk 5 from 2 to 1
Move disk 1 from 0 to 2
Move disk 2 from 0 to 1
Move disk 1 from 2 to 1
Move disk 3 from 0 to 2
Move disk 1 from 1 to 0
Move disk 2 from 1 to 2
Move disk 1 from 0 to 2
Move disk 4 from 0 to 1
Move disk 1 from 2 to 1
Move disk 2 from 2 to 0
Move disk 1 from 1 to 0
Move disk 3 from 2 to 1
Move disk 1 from 0 to 2
Move disk 2 from 0 to 1
Move disk 1 from 2 to 1
Move disk 7 from 0 to 2
Move disk 1 from 1 to 0
Move disk 2 from 1 to 2
Move disk 1 from 0 to 2
Move disk 3 from 1 to 0
Move disk 1 from 2 to 1
Move disk 2 from 2 to 0
Move disk 1 from 1 to 0
Move disk 4 from 1 to 2
Move disk 1 from 0 to 2
Move disk 2 from 0 to 1
Move disk 1 from 2 to 1
Move disk 3 from 0 to 2
Move disk 1 from 1 to 0
Move disk 2 from 1 to 2
Move disk 1 from 0 to 2
Move disk 5 from 1 to 0
Move disk 1 from 2 to 1
Move disk 2 from 2 to 0
Move disk 1 from 1 to 0
Move disk 3 from 2 to 1
Move disk 1 from 0 to 2
Move disk 2 from 0 to 1
Move disk 1 from 2 to 1
Move disk 4 from 2 to 0
Move disk 1 from 1 to 0
Move disk 2 from 1 to 2
Move disk 1 from 0 to 2
Move disk 3 from 1 to 0
Move disk 1 from 2 to 1
Move disk 2 from 2 to 0
Move disk 1 from 1 to 0
Move disk 6 from 1 to 2
Move disk 1 from 0 to 2
Move disk 2 from 0 to 1
Move disk 1 from 2 to 1
Move disk 3 from 0 to 2
Move disk 1 from 1 to 0
Move disk 2 from 1 to 2
Move disk 1 from 0 to 2
Move disk 4 from 0 to 1
Move disk 1 from 2 to 1
Move disk 2 from 2 to 0
Move disk 1 from 1 to 0
Move disk 3 from 2 to 1
Move disk 1 from 0 to 2
Move disk 2 from 0 to 1
Move disk 1 from 2 to 1
Move disk 5 from 0 to 2
Move disk 1 from 1 to 0
Move disk 2 from 1 to 2
Move disk 1 from 0 to 2
Move disk 3 from 1 to 0
Move disk 1 from 2 to 1
Move disk 2 from 2 to 0
Move disk 1 from 1 to 0
Move disk 4 from 1 to 2
Move disk 1 from 0 to 2
Move disk 2 from 0 to 1
Move disk 1 from 2 to 1
Move disk 3 from 0 to 2
Move disk 1 from 1 to 0
Move disk 2 from 1 to 2
Move disk 1 from 0 to 2

Lab Submission

Submit your main.cpp file(s).

You will submit your solution to this lab with the rest of Set5. Detailed instructions for doing this are posted in Assignment 5.


This lab is due by Friday, July 22, 2022 11:59 PM.
As with all labs you may, and are encouraged, to pair program a solution to this lab. If you choose to pair program a solution, be sure that you individually understand how to generate the correct solution.