x
Solved

# towers of hanoi

Posted on 2004-09-29
Medium Priority
508 Views
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
Question by:aik_21
• 4
• 3
• 3
• +3

LVL 46

Expert Comment

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

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

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

ID: 12186925
use a stack of ints.
0

LVL 9

Expert Comment

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

ID: 12187666
i'll go with jhshukla in implementing this problem using stacks
coz keeping track of lower disks will be much easy
0

LVL 12

Expert Comment

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

ID: 12195723
why arrays? for storing moves?
0

LVL 46

Expert Comment

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];

RemoveDisk (TowerNumber);

etc are trivial.

Kent
0

Author Comment

ID: 12196157
Hi guys,

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 46

Expert Comment

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

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 46

Accepted Solution

Kent Olsen earned 60 total points
ID: 12229015
HI Aik-21,

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];

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

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.