Solved

# towers of hanoi

Posted on 2004-09-29
491 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 45

Expert Comment

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

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

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

use a stack of ints.
0

LVL 9

Expert Comment

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

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

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

why arrays? for storing moves?
0

LVL 45

Expert Comment

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

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 45

Expert Comment

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

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

Kdo earned 20 total points
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

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.