AI Programming - 3 Jealous Husbands crossing river puzzle

[mbouster]

Dear all ,
I need your help on this. I will say how I am thinking the solution and any help will be much aprreciated.

I will denote the husbands with the following notations h1 = 11, h2=12, h3=13 and their respective wives with the numbers w1 = 21, w2 = 22, w3 = 23. I will represent the boat being at the left side with the number 0 and being at the right side of the river demoted by 1.
So the notations will be as follows:
The initial state can be described as follows:
[(People on Left Side), (People on Right Side), (Location of the boat)]
Initial State: [(11 21 12 22 13 23), (empty), (0)]
Goal State: [(empty), (11 21 12 22 13 23), (1)]
Couples: couple 1 = h1w1, couple2 = h2w2, couple 3 = h3w3
Operators: The following operators can be added to the (People on the right side list) if the boat is at the right side of the river and subtracted from that list and added to the list people on the Left Side if the boat is moving to the left side of the river.
1st operator: Take two wife’s at the other side. Depending where is the boat add or subtract from the two banks (People on the Left side) and (People on the right side). When the boat moves from left to right I add to the (People on the right side) the people I am moving from the (People on the Left side) and vice versa. The 3 possible combinations are shown below:
1. [(21 22)] = w1w2
2. [(21 23)] = w1w3
3. [(22 23)] = w2w3
2nd t operator: Take one woman to the other side. Depending where is the boat add or subtract from the two banks (People on the Left side) and (People on the right side). When the boat moves from left to right add to the (People on the right side) the people I am moving from the (People on the Left side) and vice versa. The 3 possible combinations are shown below:
1. [(21)] = w1
2. [(22)] = w2
3. [(23)] = w3
3rd operator: Take a couple at the other side. Depending where is the boat add or subtract from the two banks (People on the Left side) and (People on the right side). When the boat moves from left to right I add to the (People on the right side) the people I am moving from the (People on the Left side) and vice versa. The 3 possible combinations are shown below:
1. [(11 21)]= h1w1
2. [(12 22)] = h2w2
3. [(13 23)] = h3w3

I will create legal states functions and then how I am going to implement it using linked lists?

[daviddoria]

I will denote the husbands with the following notations h1 = 11, h2=12, h3=13 and their respective wives with the numbers w1 = 21, w2 = 22, w3 = 23

Why assign these ints to the people? Why not use something like this:

struct Person
{
public:
 enum SexEnum {Husband, Wife};
 enum SideOfRiverEnum {Start, End};
 int sex;
 int sideOfRiver;
};

...
std::vector<Person> Husbands;
Person temp;
temp.sex = Husband;
temp.sideOfRiver = Start;
Husbands.push_back(temp);

std::vector<Person> Wifes;
...

that keeps everything very understandable?

David

[daviddoria]

I will denote the husbands with the following notations h1 = 11, h2=12, h3=13 and their respective wives with the numbers w1 = 21, w2 = 22, w3 = 23

Why assign these ints to the people? Why not use something like this:

struct Person
{
public:
 enum SexEnum {Husband, Wife};
 enum SideOfRiverEnum {Start, End};
 int sex;
 int sideOfRiver;
};

...
std::vector<Person> Husbands;
Person temp;
temp.sex = Husband;
temp.sideOfRiver = Start;
Husbands.push_back(temp);

std::vector<Person> Wifes;
...

that keeps everything very understandable?

David

[mrnutty]

What information you got :

a) 3 husband and 3 wives.
b) A Boat to transport a couple/wife/2 wives

Objective: Transport 3 husband and the wives by the rules governed by (b).

So With that think and list all possible class names you need?
Do you really a Person class?
If so, should you have a Husband compose the Person class?
If so, does the husband need to know about his wife? Can you do it without?
Do you need a GameTransportation class that transports appropriately?

What else do you need? Take time to think and write down everything. After all this will be your job after your done with this "pre-game".

[mbouster]

Why assign these ints to the people? Why not use something like this:

struct Person
{
public:
 enum SexEnum {Husband, Wife};
 enum SideOfRiverEnum {Start, End};
 int sex;
 int sideOfRiver;
};

...
std::vector<Person> Husbands;
Person temp;
temp.sex = Husband;
temp.sideOfRiver = Start;
Husbands.push_back(temp);

std::vector<Person> Wifes;
...

that keeps everything very understandable?

David

So this code will solve the problem?
As i see you are using stuck and vector?
Only this code will give me the solution?

[mbouster]

What information you got :

a) 3 husband and 3 wives.
b) A Boat to transport a couple/wife/2 wives

Objective: Transport 3 husband and the wives by the rules governed by (b).

So With that think and list all possible class names you need?
Do you really a Person class?
If so, should you have a Husband compose the Person class?
If so, does the husband need to know about his wife? Can you do it without?
Do you need a GameTransportation class that transports appropriately?

What else do you need? Take time to think and write down everything. After all this will be your job after your done with this "pre-game".

I will create the classes you mention here. My question is how to associate the persons transfered with the boat and between the classes. I am a junior C++ student. Our teacher said we could use linked lists or double linked lists. I will be able to create the classes and the code...
If you could help me with the spine it will be very helpfull.
I will try to write the pseudocode to see if I come up wiht something.

[mbouster]

Dear all ,
I need your help on this. I will say how I am thinking the solution and any help will be much aprreciated.

I will denote the husbands with the following notations h1 = 11, h2=12, h3=13 and their respective wives with the numbers w1 = 21, w2 = 22, w3 = 23. I will represent the boat being at the left side with the number 0 and being at the right side of the river demoted by 1.
So the notations will be as follows:
The initial state can be described as follows:
[(People on Left Side), (People on Right Side), (Location of the boat)]
Initial State: [(11 21 12 22 13 23), (empty), (0)]
Goal State: [(empty), (11 21 12 22 13 23), (1)]
Couples: couple 1 = h1w1, couple2 = h2w2, couple 3 = h3w3
Operators: The following operators can be added to the (People on the right side list) if the boat is at the right side of the river and subtracted from that list and added to the list people on the Left Side if the boat is moving to the left side of the river.
1st operator: Take two wife’s at the other side. Depending where is the boat add or subtract from the two banks (People on the Left side) and (People on the right side). When the boat moves from left to right I add to the (People on the right side) the people I am moving from the (People on the Left side) and vice versa. The 3 possible combinations are shown below:
1. [(21 22)] = w1w2
2. [(21 23)] = w1w3
3. [(22 23)] = w2w3
2nd t operator: Take one woman to the other side. Depending where is the boat add or subtract from the two banks (People on the Left side) and (People on the right side). When the boat moves from left to right add to the (People on the right side) the people I am moving from the (People on the Left side) and vice versa. The 3 possible combinations are shown below:
1. [(21)] = w1
2. [(22)] = w2
3. [(23)] = w3
3rd operator: Take a couple at the other side. Depending where is the boat add or subtract from the two banks (People on the Left side) and (People on the right side). When the boat moves from left to right I add to the (People on the right side) the people I am moving from the (People on the Left side) and vice versa. The 3 possible combinations are shown below:
1. [(11 21)]= h1w1
2. [(12 22)] = h2w2
3. [(13 23)] = h3w3

I will create legal states functions and then how I am going to implement it using linked lists?

I came up with this code
// insert at the end of the list an element
void linklist::addend(int num)
{
node *q,*t;
//if the list is empty
if(p==NULL)
{
p=new node;
p->data=num;
p->link=NULL;
}
else
{
q=p;
while(q->link!=NULL)
q=q->link;
t=new node;
t->data=num;
t->link=NULL;
q->link=t;
}
}
//delete a specified node from the linked list

void linklist:: del(int num)
{
node *q,*r;
q=p;
//if node to be deleted is the first node
if (q->data==num)
{
p=p->link;
delete q;
return;
}
r=q;
while(q!=NULL)
{
if(q->data==num)
{
r->link=q->link;
delete q;
return;
}
r=q;
q=q->link;
}
}

//code to display the elements of the list
void linklist::display()
{
node *q;
clrscr();
cout<<endl;
for(q=p;q!=NULL;q=q->link)
cout<<" "<<q->data;
}

. Which I have found online and in books for reference.
So I will create the functions needed (why you call them classes?) and I will call this functions with my parameters from the main function right?
A spine or some more advice it is much apreciated :)

[daviddoria]

What is a spine? A class is much different than a function. It is an object which contains data and functions.

Please use code tags when you post code.

[mbouster]

What is a spine? A class is much different than a function. It is an object which contains data and functions.

Please use code tags when you post code.

A spine is a skeleton :

lets says

class Person contains wife and husbands

.
Class valid states or rules

Class crossing for the different crossings.

One more question.
I will create the main functiion and code the appropriate solution or I will create a class and by calling the fucntion search all the possible nodes for the solution.

Can you please give me a reference what I must study in order to implement this solution. C++ Classes and functions, link lists or vectors???

:)