Solved

towers of hanoi

Posted on 2004-09-29
13
491 Views
Last Modified: 2010-04-15
Hi there all,
I am working on the towers of hanoi problem. I do know the algorithm for it but there is some fancy stuff i need to do with it. I need to print all the moves for the discs as in below
|_        |       |
|_ _      |       |
|_ _ _   |       |  

|        |       |
|_ _    |       |
|_ __  |_      |  

|         |        |
|         |        |
|_ _ _  |_      |_ _   and so on....

I need to use structures for the pegs.
I am aware i need to keep the track of the peg numbers and the corresponding discs.  I am also confused in movin the discs from one peg to another. I just need to know that how would i incorporate this into a structure so that it'll be convenient to move items in the structure.
Here is my code(although its not correct syntax wise, but this is what i am trying to do)
#include<stdio.h>

typedef char TowerEntry;    
typedef struct towernode{      
        TowerEntry peg,disc;  
        struct TowerNode *next;
}TowerNode;

typedef struct tower{
        TowerNode *top;
        char initialdisc;
}Tower;

TowerNode *MakeNode(TowerEntry item1, TowerEntry item2);
void Move(int num, Tower *t1, Tower *t2, Tower *t3);

int N; /*global variable*/

TowerNode *MakeNode(TowerEntry item1, TowerEntry item2){
        TowerNode *nodepointer;
        if((nodepointer=malloc(sizeof(TowerNode)))==NULL)
            printf("Out of memory\n");
        else
        {
                nodepointer->peg=item1;
                nodepointer->disc=item2;
                nodepointer->next = NULL;
               
        }
        return nodepointer;
}

/*to be used initially*/
void TowerPush(TowerEntry item1, TowerEntry item2, Tower *s){
        TowerNode *np=MakeNode(item1, item2);
        if(np==NULL)
                printf("Can't push on an non existing node\n");
        else
        {
                np->next=s->top;
                s->top=np;
        }

}
void CreateTower(Tower *s){
        s->top=NULL;
        s->size=N;
}

int main(int argc, char *argv[]){
     
        int i;
        N=atoi(argv[1]);
        Tower *t1,*t2,*t3;
        CreateTower(t1);
        CreateTower(t2);
        CreateTower(t3);
        for(i=0;i<N;i++)
        {
         printf("%s|%s   %s|     %s|\n   ",t1,t1->initialdisc,t2,t3);
  }
        Move(N,t1,t2,t3);
        return 0;
}

void Move(int count, Tower *one, Tower *two, Tower *three)
{
    if (count > 0) {
        Move(count-1, one, two, three);
        printf("Move a disk from %d to %d.\n", one, three);
        Move(count-1, two, three, one);
    }
}

Could someone, give me suggestions on what changes i need to make or what am i missing or what strategy should i follow?

Thank You

Aik_21


0
Comment
Question by:aik_21
  • 4
  • 3
  • 3
  • +3
13 Comments
 
LVL 45

Expert Comment

by:Kdo
Comment Utility
Hi aik_21,

Unless your assignment specifically tells you to use a linked list, throw it in the trash.  This isn't an application for it.

Instead, create an array of nodes.

Finding node 5 is a lot easier in an array than a linked list.  :)


Kent
0
 

Author Comment

by:aik_21
Comment Utility
Hi Kent,

Correct me if i am wrong, but isn't an array of nodes similar to linked lists?  I mean linked lists have nodes!

Thanks

Aik_21
0
 
LVL 23

Expert Comment

by:brettmjohnson
Comment Utility
Yes, but an array makes it much easier to access the nodes.  
A linked list is usually accessed sequentially, whereas an array can be accessed randomly.

But then again, I can't figure out why you "need to use structures" for the Tower of Hanoi game.
Structures are not really any more suitable a tool to use for the problem than linked lists are.
(A 3-peg ToH puzzle needs only an array of 3 nibbles  to solve).

Are CS instructors actually so lame that they cannot think up suitable problems for which the
concept-to-be-taught is actually useful?

0
 
LVL 9

Expert Comment

by:jhshukla
Comment Utility
use a stack of ints.
0
 
LVL 9

Expert Comment

by:jhshukla
Comment Utility
its true that you can only access the top element but in towers of hanoi you are not allowed to other discs. can't think of a better way to store unless it is requierd to access lower discs.
0
 
LVL 6

Expert Comment

by:Amritpal Singh
Comment Utility
i'll go with jhshukla in implementing this problem using stacks
coz keeping track of lower disks will be much easy
0
Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

 
LVL 12

Expert Comment

by:stefan73
Comment Utility
Yes, the ToH is basically copying one stack to another in the same order, using only a 3rd stack as temporary storage.

solving ToH with nested target.push(source.pop()) is quite an elegant way.

And yes, you should use an array. The maximum size is known, as ToH is O(2^n). If you have a max array size of, say, 32, you'll never likely run out of tower stacks :-)

Cheers!

Stefan
0
 
LVL 9

Expert Comment

by:jhshukla
Comment Utility
why arrays? for storing moves?
0
 
LVL 45

Expert Comment

by:Kdo
Comment Utility

One of the features of these kinds of games (simulations) is that you often want to change the dynamics of the game.  Increase the number of towers, number of disks, etc.  This can easily be done with both arrays and lists.

typedef struct
{
  int DiskNumber;
}  disk_t;

typedef struct
{
  int DiskCount;  /*  Number of disks on the tower  */
  disk_t Disk[MAX_DISKS];
}  tower_t;

tower_t Tower[MAX_TOWERS];

AddDisk (TowerNumber, DiskNumber);
RemoveDisk (TowerNumber);

etc are trivial.



Kent
0
 

Author Comment

by:aik_21
Comment Utility
Hi guys,
first of all thank you very much for your answers.

I need to use stacks for this program, not cuz we have to but i do have a sound understanding for the topic and need to do it in a way I would understand.  I needed to use the move function such that it uses POP and PUSH functions for the tower entries to be moved.

Can someone tell me if the structure below makes sense, or i would fall into problems?

typedef char TowerEntry;    
typedef struct towernode{      
        TowerEntry peg; // '|'
TowerEntry disc; // '_'
        struct TowerNode *next;
}TowerNode;

typedef struct tower{
        TowerNode *top;
}Tower;


Thank You

Aik_21
0
 
LVL 45

Expert Comment

by:Kdo
Comment Utility

It makes sense.  Though you're mixing typedefs and structs in the TowerNode.  

A simple forward reference will allow you to typedef the structure and remove the need for a struct qualifier within the structure.


Kent


0
 

Author Comment

by:aik_21
Comment Utility
Hey Kent,

Thank you for the quick tip!

I have made some changes to my structure.
typedef char Disc;
typedef struct peg{
        Disc dsc[5]; // '_'
}Peg; // '|'
typedef struct towernode{
        Peg pos[5];
        struct TowerNode *next;
}TowerNode;

typedef struct tower{
        TowerNode *top;
}Tower;  

This is what i am saying: have a type for Bars '|', type for Discs '_', now have a Peg structure and add array of bars to it!
So that i could do Peg abc[5];
then i could say abc[i]->dsc[i]='_' and abc[i]='|'  // i dont know if i got the right syntax/logic
i.e. |_ _ _

Was that correct logically/syntax wise or i am missing something?


Thank You

Aik-21
ps: i know i m bad at this :D, i m still learning :D
0
 
LVL 45

Accepted Solution

by:
Kdo earned 20 total points
Comment Utility
HI Aik-21,

Sorry for not getting back sooner, I missed your reply.


You're back to making things harder than they have to be.  :)

You're only managing two type of objects.  Pegs and disks.  Pegs are "fixed" commodities.  The don't move, they don't change shape, they don't do anything, except house the disks.  The Peg definitions are kept as arrays.

The definition of the disks is equally stable.  Define a disk structure for every disk in the game and initialize it to the correct values.

Now the only things that you have are:

Pegs peg[3];
Disks disk[SomeNumber];


And the entire structure is controlled with two if statements:


if (peg[0]->disk != NULL)   /*  This peg has a disk on it  */

if (disk->next != NULL)   /*  this disk has a disk on top of it  */


The 3 pegs are a simple array and the disks on top of the pegs are kept as linked lists.
Kent

0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.

744 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now