Solved

towers of hanoi

Posted on 2004-09-29
13
493 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
ID: 12186256
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
ID: 12186297
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
ID: 12186631
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
ID: 12186925
use a stack of ints.
0
 
LVL 9

Expert Comment

by:jhshukla
ID: 12186934
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
ID: 12187666
i'll go with jhshukla in implementing this problem using stacks
coz keeping track of lower disks will be much easy
0
Microsoft Certification Exam 74-409

Veeam® is happy to provide the Microsoft community with a study guide prepared by MVP and MCT, Orin Thomas. This guide will take you through each of the exam objectives, helping you to prepare for and pass the examination.

 
LVL 12

Expert Comment

by:stefan73
ID: 12188462
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
ID: 12195723
why arrays? for storing moves?
0
 
LVL 45

Expert Comment

by:Kdo
ID: 12196148

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
ID: 12196157
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
ID: 12196252

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
ID: 12197076
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
ID: 12229015
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

Problems using Powershell and Active Directory?

Managing Active Directory does not always have to be complicated.  If you are spending more time trying instead of doing, then it's time to look at something else. For nearly 20 years, AD admins around the world have used one tool for day-to-day AD management: Hyena. Discover why

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Beginner Probleme with my IDE Code::Blocks C++ 5 233
Which version of C should I use when Perl is too slow? 13 173
Trouble linking program with -lcrypt 3 141
Problem to ASCII 1 166
Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

911 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

21 Experts available now in Live!

Get 1:1 Help Now