Solving Towers of Hanoi with Linked List Based Stack
Overview
The Towers of Hanoi is a mathematical puzzle that is a popular data structures and algorithms problem. The puzzle was first introduced in 1883 by Edouard Lucas, a French mathematician known for his study of the Fibonacci sequence (another popular computer science problem).
The problem requires shifting disks amongst a source tower, temporary tower, and destination tower. The goal is to shift all disks from the source tower to the destination tower, however, there are constraints that must be followed. These constraints require that only one disk may be moved at a time, and a larger disk cannot be placed on top of a smaller disk.
The data structure we will use to implement this algorithm will be the stack. We will take the challenge a step further by using a linked-list based stack. The goal if this post is to focus on the Towers of Hanoi, though we will briefly cover stacks.
Stacks
A stack is a linear data structure that follows LIFO (last-in first out) order. Common procedures of a stack are:
- push(new item) — adds new item to top of stack
- pop() — removes item from top of stack
- count() — gets count of items in stack
- peek() — returns element at the top of stack
- isEmpty() — checks if stack is empty or not
Stacks often have predefined capacities and will signal whether it is in an underflow state (empty) or overflow state (full) when attempting to perform operations on it. A linked list implementation solves this problem, as the stack is able to grow dynamically; in other words, we don’t have to worry about the underflow or overflow states. We do have to worry about the stack growing too big and overconsuming memory, however that is out of the scope for this post. To learn more about stacks, go here.
Algorithm
We will now go into the Towers of Hanoi algorithm. We are going to utilize an iterative approach. You can also use recursive approaches, which some may find simpler to implement, however, recursion can often trade off simplicity for memory consumption due to function call overhead.
We will need to find out the number of moves needing to be made in order to determine how long our loop runs; we can use the formula (2^n)-1.
Next, we determine if the number of disks is even or odd, as we will have different strategies for each approach. If the number of disks is even, we can interchange the the destination tower and the temporary tower. However, we will not implement that approach here for the sake of simplicity and a general introduction to the algorithm.
Code
The code for the implementation is below, for the actual source code from my github, follow this link. The first part of main() is building and testing the stack data structure.
#include <iostream>
#include <math.h>struct Node{
int diam;
Node* next;}; class Stack
{
private:
Node* top;
public:
Stack();
bool push(int);
int pop();
int peek();
int count();
void print();
bool isEmpty();
}; Stack::Stack(){
top = NULL;
} bool Stack::push(int diam){
bool status = false;
Node* temp = new Node();
temp->diam = diam;
temp->next = top;
top = temp;
if(top->diam == diam){
status = true;
}
return status;
}bool Stack::isEmpty(){
bool status = false;
if(top == NULL){
status = true;
}
return status;
} int Stack::pop(){
int value = INT_MIN;
if(top){
Node* temp = top;
value = temp->diam;
top = temp->next;
delete(temp);
}
return value;
} int Stack::count(){
int count = 0;
Node* temp = top;
while(temp){
count++;
temp = temp->next;
}
return count;
} int Stack::peek(){
int value = INT_MIN;
if(top){
value = top->diam;
}
return value;
} void Stack::print(){
Node* temp = top;
while(temp){
std::cout << temp->diam << ' ';
temp = temp->next;
}
} void moveDisk(Stack *source, Stack *destination){
int tower1Top = source->pop();
int tower2Top = destination->pop();
if(tower1Top == INT_MIN){
source->push(tower2Top);
}
else if(tower2Top ==INT_MIN){
destination->push(tower1Top);
}
else if(tower1Top > tower2Top){
source->push(tower1Top);
source->push(tower2Top);
}
else{
destination->push(tower2Top);
destination->push(tower1Top);
}
}int main() {
Stack towerOne;
Stack towerTwo;
Stack towerThree;
int towerSize = 10; if(towerOne.isEmpty() && towerTwo.isEmpty() && towerThree.isEmpty()){
std::cout << "Three empty stacks created" << std::endl;
}
std::cout << '\n'; std::cout << "Putting " << towerSize << " plates of subsequently smaller diameter on towerOne" << std::endl;
for(int i=towerSize; i>0; i--){
towerOne.push(i);
}
std::cout << '\n';
std::cout << "Printing Tower One: " << std::endl;
towerOne.print();
std::cout << '\n';
std::cout << '\n'; std::cout << "Testing pop() on Tower One (removing top value):" << std::endl;
std::cout << towerOne.pop() << std::endl;
std::cout << "Tower Size is now " << towerSize-1 << std::endl;
std::cout << '\n'; std::cout << "Printing updated list:" << std::endl;
towerOne.print();
std::cout << '\n';
std::cout << '\n'; std::cout << "Testing peek()" << std::endl;
std::cout << towerOne.peek() << std::endl;
std::cout << '\n'; std::cout << "Testing count()" << std::endl;
std::cout << towerOne.count() << std::endl;
std::cout << '\n';
int total_moves = pow(2, towerOne.count()) - 1;
std::cout << "Running Towers of Hanoi algorithm" << std::endl;
if(towerOne.count()%2 != 0){
for(int i=1; i<=total_moves; i++){
if(i%3==1){
moveDisk(&towerOne, &towerThree);
}
else if(i%3==2){
moveDisk(&towerOne, &towerTwo);
}
else if(i%3==0){
moveDisk(&towerTwo, &towerThree);
}
}
}
else if(towerOne.count()%2==0){
for(int i=1; i<=total_moves; i++){
if(i%3==1){
moveDisk(&towerOne, &towerTwo);
}
else if(i%3==2){
moveDisk(&towerOne, &towerThree);
}
else if(i%3==0){
moveDisk(&towerTwo, &towerThree);
}
}
} std::cout << "Checking Tower Three count is equal to " << towerSize-1 << std::endl; std::cout << "Tower Three Count: " << towerThree.count() << std::endl;
std::cout << "\n"; std::cout << "Checking Tower Three elements are in ascending order " << std::endl;
towerThree.print();
std::cout << "\n";
}
