Tower of Hanoi puzzle

BTE320 - Introduction to Programming

(Spring 2019) by Dr. Leon Espinosa.

Assignment # 5 due day 04/15/2019 1:00pm. HARD DEADLINE!

This is the Tower of Hanoi puzzle: You have three stacks of rings. Each ring is smaller than the

one it sits on. The challenge is to move all the rings from the first stack to the third, subject to

these constraints:

• You can move only one ring at a time.

• You can place a ring only on top of a larger ring, never a smaller.

It sounds easy, until you try it! Consider a stack four rings high: You start by moving the top ring

from the first stack, but where do you move it, and what do you do after that?

To solve the problem, assume we already know how to move a group of N–1 rings. Then, to

move N rings from a source stack to a destination stack, do the following:

Move N–1 rings from the source stack to the (currently) unused, or “other,” stack.

Move a single ring from the source stack to the destination stack.

Move N–1 rings from the “other” stack to the destination stack.

This is easier to envision graphically. Video: https://www.youtube.com/watch?v=LOuFQiL9Kes

First, the algorithm moves N–1 rings from the source stack to the “other” stack (“other” being

the stack that is neither source nor destination for the current move). In this case, N is 4 and N–1

is 3, but these numbers will vary.

After this recursive move, at least one ring is left at the top of the source stack. This top ring is

then moved: This is a simple action, moving one ring from source to destination.

Finally, we perform another recursive move, moving N–1 rings from “other” (the stack that is

currently neither source nor destination) to the destination.

What permits us to move N–1 rings in steps 1 and 3, when the constraints tell us that we can

move only one?

Remember the basic idea of recursion. Assume the problem has already been solved for the case

N–1, although this may require many steps. All we have to do is tell the program how to solve

the Nth case in terms of the N–1 case. The program “magically” does the rest.

It’s important, also, to solve the terminal case, N = 1. But that’s trivial. Where one ring is

involved, we simply move the ring as desired.

The following program shows the C++ code that implements this algorithm with a recursive

approach: #include "stdafx.h" //VStudio users #include <cstdlib> #include <iostream> using namespace std; void move_rings(int n, int src, int dest, int other); int main() { int n = 5; // Stack is 3 rings high move_rings(n, 1, 3, 2); // Move stack 1 to stack 3 system("PAUSE"); //VStudio users return 0; } void move_rings(int n, int src, int dest, int other) { if (n == 1) { cout << "Move from " << src << " to " << dest << endl; } else { move_rings(n - 1, src, other, dest); cout << "Move from " << src << " to " << dest << endl; move_rings(n - 1, other, dest, src); } }

For comparison purposes, look at the following program that shows the C++ code that

implements this same algorithm but with a non-recursive approach:

#include "stdafx.h" //VStudio users #include <iostream> using std::cout; using std::cin; using std::endl; bool isEven(int disks); //function prototype isEven int moves(int disks); //function prototype moves void MoveTower(int disks, int numberOfMovesToSolve, int src, int tmp, int dst); //function prototype MoveTower void MoveSingle(int src, int dst); //function prototype MoveSingle int whichDisk(int movement, int disks); //function prototype whichDisk

int patronNumber(int movement, int whichDisk, int disks); //function prototype patronNumber int main() { int disks; int src, tmp, dst; int numberOfMovesToSolve; cout << "Number of disks: "; cin >> disks; cout << "Initial peg: "; cin >> src; cout << "Temporal peg: "; cin >> tmp; cout << "Destination peg: "; cin >> dst; numberOfMovesToSolve = moves(disks); MoveTower(disks, numberOfMovesToSolve, src, tmp, dst); system("pause"); //VStudio users return 0;//indicates success }//end main bool isEven(int disks) { bool isEven; if (disks % 2 == 0) isEven = true; else isEven = false; return isEven; }//end function isEven int moves(int disks) { int moves = 0; for (int i = 1; i <= disks; i++) { moves = (moves * 2) + 1; }//end loop for return moves; }//end function moves void MoveTower(int disks, int numberOfMovesToSolve, int src, int tmp, int dst) { if (!isEven(disks)) { //isNotEven for (int movement = 1; movement <= numberOfMovesToSolve; movement++) { switch (patronNumber(movement, whichDisk(movement, disks), disks)) { case 1: if (!isEven(whichDisk(movement, disks))) MoveSingle(src, dst); else MoveSingle(src, tmp); break; case 2: if (!isEven(whichDisk(movement, disks))) MoveSingle(dst, tmp); else MoveSingle(tmp, dst); break; case 3: if (!isEven(whichDisk(movement, disks))) MoveSingle(tmp, src);

else MoveSingle(dst, src); break; }//end switch }//end loop for } else { //isEven for (int movement = 1; movement <= numberOfMovesToSolve; movement++) { switch (patronNumber(movement, whichDisk(movement, disks), disks)) { case 1: if (!isEven(whichDisk(movement, disks))) MoveSingle(src, tmp); else MoveSingle(src, dst); break; case 2: if (!isEven(whichDisk(movement, disks))) MoveSingle(tmp, dst); else MoveSingle(dst, tmp); break; case 3: if (!isEven(whichDisk(movement, disks))) MoveSingle(dst, src); else MoveSingle(tmp, src); break; }//end switch }//end loop for }//end if...else }//end function MoveTower void MoveSingle(int src, int dst) { cout << src << "--->" << dst << '\n'; }//end function MoveSingle int whichDisk(int movement, int disks) { int whichDisk; int start = 1; int increment = 2; int movements = moves(disks); for (int i = 1; i <= disks; i++) { for (int j = start; j <= movements; j += increment) { if (movement == j) { whichDisk = i; }//end if }//end inner loop start *= 2; increment *= 2; }//end outer for loop return whichDisk; }//end function whichDisk int patronNumber(int movement, int whichDisk, int disks) { int patronNumber = 0; int increment = 2; int start = 1; for (int i = 1; i <= disks; i++) { if (i == whichDisk) { for (int j = start; j <= movement; j += increment) { patronNumber++; if (patronNumber == 3 && j != movement) patronNumber = 0; }//end inner for }//end if

start *= 2; increment *= 2; }//end for loop return patronNumber; }//end patronNumber

Write a report where you describe the results after you follow these instructions:

1. Study both solutions (iterative vs recursive). 2. Do several runs of each version and take screenshots. 3. Compare results (complexity, time, etc.). 4. Compare approaches (logic behind). 5. Select one of the two versions and modify it in order to accomplish something different

(e.g. add elements, provide more options, improve friendliness of the dialogs; this is your

opportunity to be creative!).

6. Take screenshots of the new implementation running (including the results); be sure I can see your computer desktop with something identifying it is you, with the day & time.

Document many runs of your code.

7. Upload your word/pdf file to Blackboard.