Printing the Tower of Hanoi Linearly

Question

I am having trouble printing the tower of hanoi in C.

My guess is that the cause of this is due to the algorithm is being run recursively. and the variables pegSource, pegSpare, and pegDest are getting switched up. causing it to print improperly.

My current Output when the input is 3 is:

              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
             +|+                   |                    |                                                
            ++|++                  |                    |                                                
           +++|+++                 |                    |                                                
     XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX                                       
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
            ++|++                  |                    |                                                
           +++|+++                 |                   +|+                                               
     XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX                                       
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
             +|+                 ++|++               +++|+++                                             
     XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX                                       
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                   +|+                                               
           +++|+++                 |                  ++|++                                              
     XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX       
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
             +|+                   |                    |                                                
            ++|++                  |                 +++|+++                                             
     XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX                                       
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
            ++|++               +++|+++                +|+                                               
     XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX                                       
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                  ++|++                  |                                                
             +|+                +++|+++                 |                                                
     XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX                                       
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                    |                    |                                                
              |                   +|+                   |                                                
              |                  ++|++                  |                                                
              |                 +++|+++                 |                                                
     XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX    

Where as the desired output is:

            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
           +|+                       |                        |            
          ++|++                      |                        |            
         +++|+++                     |                        |            
   XXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXX   

            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
          ++|++                      |                        |            
         +++|+++                    +|+                       |            
   XXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXX   

            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
         +++|+++                    +|+                     ++|++            
   XXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXX   

            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                       +|+            
         +++|+++                     |                      ++|++            
   XXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXX   

            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                       +|+            
            |                     +++|+++                   ++|++            
   XXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXX   

            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
           +|+                    +++|+++                   ++|++            
   XXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXX   

            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                      ++|++                      |            
           +|+                    +++|+++                     |
   XXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXX   

            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                        |                        |            
            |                       +|+                       |            
            |                      ++|++                      |            
            |                     +++|+++                     |
   XXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXX      XXXXXXXXXXXXXXXXXXX

Here is my C Code:
I have tried putting the PrintPegs(pegSource, pegDest, pegSpare); line in several places in the TOH function as well as the MoveDisk function. Of course none worked out. if possible, I would like to be able to print the desired output above instead of my current output.

#include <stdio.h>
#include <stdlib.h>

void PrintPegLine(int layer, int peg[]){
    switch (peg[layer]){
        case 0:
            printf("          |          ");
            break;
        case 1:
            printf("         +|+         ");
            break;
        case 2:
            printf("        ++|++        ");
            break;
        case 3:
            printf("       +++|+++       ");
            break;
        case 4:
            printf("      ++++|++++      ");
            break;
        case 5:
            printf("     +++++|+++++     ");
            break;
        case 6:
            printf("    ++++++|++++++    ");
            break;
        case 7:
            printf("   +++++++|+++++++   ");
            break;
        case 8:
            printf("  ++++++++|++++++++  ");
            break;
        default:
            printf(" XXXXXXXXXXXXXXXXXXX ");
            break;

    }
}

void PrintPegs(int pegSource[], int pegDest[], int pegSpare[]) {
    int layer;
    for (layer=0; layer<9; layer++){
        PrintPegLine(layer, pegSource);
        PrintPegLine(layer, pegDest);
        PrintPegLine(layer, pegSpare);
        printf("\n");
      }
}

void MoveDisk(int pegSource[], int pegDest[]){
    int i,j;
    int temp;

    for (i=0; i<9; i++){
        if (pegSource[i] != 0){
            temp = pegSource[i];
            pegSource[i]=0;
            break;
        }
    }

    for (j=0; j<9; j++){
        if (pegDest[j] != 0){
            pegDest[j-1]=temp;
            break;
        }
    }
}

void TOH(int n, int pegSource[], int pegDest[], int pegSpare[]) {
   if (n > 0) {
      TOH(n - 1, pegSource, pegSpare, pegDest);
      PrintPegs(pegSource, pegDest, pegSpare);
      MoveDisk(pegSource, pegDest);
      TOH(n - 1, pegSpare, pegDest, pegSource);
   }
}



int main(int argc, char **argv)
{
    int n = atoi(argv[1]);
    if (n>8 || n<2){
        printf("invalid input\n");
        exit(0);
    }
    int pegSource[9] = {0,0,0,0,0,0,0,0,9};
    int pegDest[9] = {0,0,0,0,0,0,0,0,9};
    int pegSpare[9] = {0,0,0,0,0,0,0,0,9};
    int i;
    int j = 1;
    for (i=8-n; i<8; i++){
        pegSource[i]=j;
        j++;
    }
      TOH(n, pegSource, pegDest, pegSpare);
      PrintPegs(pegSource, pegDest, pegSpare);
      printf("DONE\n");
    return 0;
}

Thanks

Answer 1

Your algorithm for solving the Tower of Hanoi is fine. The problem is with how you call PrintPegs(). When you recurse, you correctly permute the order of pegSource, pegSpare and pegDest -- but this also permutes the order in which they are printed out, which you don't want.

A quick fix is to pass the arrays in twice, once to be permuted, and once to be printed, like so:

void TOH(int n, int pegSource[], int pegDest[], int pegSpare[], int print1 [], int print2 [], int print3[]) {
   if (n > 0) {
      TOH(n - 1, pegSource, pegSpare, pegDest, print1, print2, print3);
      PrintPegs(print1, print2, print3);
      MoveDisk(pegSource, pegDest);
      TOH(n - 1, pegSpare, pegDest, pegSource, print1, print2, print3);
   }
}

int main(int argc, char **argv)
{
    int n = atoi(argv[1]);
    int pegSource[9] = {0,0,0,0,0,0,0,0,9};
    int pegDest[9] = {0,0,0,0,0,0,0,0,9};
    int pegSpare[9] = {0,0,0,0,0,0,0,0,9};
    int i;
    int j = 1;

    if (n>8 || n<2){
        printf("invalid input\n");
        exit(0);
    }
    for (i=8-n; i<8; i++){
        pegSource[i]=j;
        j++;
    }

    TOH(n, pegSource, pegDest, pegSpare, pegSource, pegDest, pegSpare);
    PrintPegs(pegSource, pegDest, pegSpare);
    printf("DONE\n");
    return 0;
}

Doing so, I get the output:

          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
         +|+                   |                    |
        ++|++                  |                    |
       +++|+++                 |                    |
 XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
        ++|++                  |                    |
       +++|+++                +|+                   |
 XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
       +++|+++                +|+                 ++|++
 XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                   +|+
       +++|+++                 |                  ++|++
 XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                   +|+
          |                 +++|+++               ++|++
 XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
         +|+                +++|+++               ++|++
 XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                  ++|++                  |
         +|+                +++|+++                 |
 XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                    |                    |
          |                   +|+                   |
          |                  ++|++                  |
          |                 +++|+++                 |
 XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX  XXXXXXXXXXXXXXXXXXX

Answer 2

i am not sure its possible to write it as you wish.. because whenever you call the recursion you actually have to switch between the pegs and than you never switch it back.. so for most of the recursion calls its actually goes like this

edit: actually i am starting to think that you can do it if you will use another function for the last part of Tower of Hanoi recursion