Tower of Hanoi - C++

Tower of Hanoi - C++

This brief article is about the tower of Hanoi. Wrote this super simple C++ for a student and thought maybe it could be helpful.

It works on the idea that in order to move n disks from pile 1 to 3 we need to first move the first n-1 disks to a support pole (choosing the right on is part of the solution, see the code for further detail), then move disk n in the correct position, and finally move the first n-1 disks from support pole to the correct location. Let the recursion does the magic!

The base case is when we have only one disk to move. Simply move the disk in the correct pile.

Tower of Hanoi - C++ Code


#include <iostream>
#include<vector>
#include <stack>
#include<algorithm>
#include <unistd.h>
using namespace std;

int max3(int a, int b, int c){
    return max(max(a,b),c);

}

void printNtimes(char c, int n){
    for(int i=0 ; i<n; i++) printf("%c",c); } int ndisks; int sleeptime=100000; int nmoves=0; //prints the current status of the piles void drawHanoi(auto& piles){ int m = max3(piles[0].size(),piles[1].size(),piles[2].size()); int sep[3] = {ndisks,ndisks,ndisks}; for(int i=ndisks ; i>=0; --i){
       for(int j=0; j<3; j++){ printf(" | "); if(piles[j].size() > i){
            
        int n = piles[j][i]+1;
        printNtimes('=',n);
        printNtimes(' ',sep[j]-n+1);
 
         } else
        printNtimes(' ',sep[j]+1);
        printf(" | ");

      }
      printf("\n");

    }

  printf("\n\n");
  usleep(sleeptime);
}


//function that solves the hanoi tower problem
void solveHanoi(int start, int end, int from, int to, auto& piles){
    //which pile should we use as support pile?	
    int support = (from + to)%4;
    support = support == 0 ? 2 : support;

     if(end-start == 0 ){

        piles[to-1].push_back(piles[from-1].back());
        piles[from-1].pop_back();
        drawHanoi(piles);
        nmoves++;
     }

     else{
        solveHanoi(start,end-1,from,support,piles);
        solveHanoi(end,end,from,to,piles);
        solveHanoi(start,end-1,support,to,piles);

     }

}



int main(){

    //two integers input from standard input. NUmber of piles and sleep time used for visualization purtposes.
//echo "8 1000000" | ./hanoi will execute the solver on 10 disks with a visualization refresh of 1 second
    int np; cin>>np;cin>>sleeptime;
    vector<vector<int>> piles(3, vector<int>());
    ndisks=np;
//initialize the disks on pile one
    for(int i=np; i>=0; i--)
        piles[0].push_back(i);

    

    solveHanoi(0,np,1,3,piles);
    printf("solved using %d moves\n",nmoves);
    return 0;

}

 

You can try to compile and execute this code online at the following link: http://goo.gl/PRhbsF

Make sure you compile using std=c++14 standard


g++ -std=c++14 -o main *.cpp

Be the first to leave a comment. Don’t be shy.

Join the Discussion

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>