# [Prolog] The Three Jealous Men and Their Wives

Three men, travelling with their wives, came to a river which they wanted to cross. The one available boat would accomodate only two people. Since the husbands were very jealous, no woman could be with a man unless her own husband was present. Under these severe handicaps, how can they get across the river using the one boat?

(Source: Mr. P’s Math Page)

I haven’t had time to search for the solution on the internet so I am not very sure what kind of method that they have used, not to mention that if existing a solution that is similar to mine. So whatever, I will share it on here.

In this solution, I use the state space search method (I believe that every computer science student must have learnt this so I will not explain it again. If you, for some reason, do not know this method then please google about it on the internet for find some introductory books of artificial intelligence).

My state representation in Prolog is a list with below structure:

[Boat, [Husband1, Wife1], [Husband2, Wife2], [Husband3, Wife3]]

- Boat: 0 if the boat is on the left bank, 1 if the boat is on the right bank.
- Husband1: 0 if the Husband1 is on the left bank, 1 if the Husband1 is on the right bank.
- Same goes for Wife1, Husband2, Wife2, Husband3, Wife3.

Before delving into further, I want to make some observations:

- For variable T that can only hold 2 possible values 0 or 1: if T = 1, 1 – T = 0 ; if T = 0, 1 – T = 1.
- People can only move from the left bank to the right bank if the boat is currently on the left bank. More conretely: If Boat = 0, Husband1 can use the boat to move to the opposite bank if and only if Husband1 = 0 ; in general, Husband1 can use the boat to move to the opposite bank if and only if Husband1 = Boat.

I also make some conventions:

- B stands for Boat.
- H stands for Husband.
- W stands for Wife.
- T stands for the tail of a list.

Possible actions to transfer from a state to another state are:

- Let a couple be on the same boat to move to the opposite bank:

12move2([[H,W]|T],[[H1,W1]|T],B) :- H=B, W=B, H1 is 1-H, W1 is 1-W.%[[H,W]|T] is the current state while [[H1,W1]|T] is the next state.

However, that code line alone allows only the first couple to be on the same boat, how about the other couples? Let’s traverse the list:

1move2([X|T1],[X|T2],B) :- move2(T1,T2,B). - Let 1 person be on the boat to move to the opposite bank, this one can be a husband or a wife:

123move1([[H,W]|T],[[H1,W]|T],B,1) :- H=B, H1 is 1-H.move1([[H,W]|T],[[H,W1]|T],B,2) :- W=B, W1 is 1-W.move1([X|T1],[X|T2],B,Gender) :- move1(T1,T2,B,Gender).

Gender = 1 means that person is male, Gender = 2 means that person is female.

We have been able to move a couple or a person to the opposite bank. Let’s combine this ability into one predicate:

1 2 |
move(X,Y,B) :- move2(X,Y,B). move(X,Y,B) :- move1(X,Y,B,_). %We doesn't care the gender of the moving person. |

Now comes the interesting part: Don’t you see that we lack one possible action of the state space? That is:

- Let 2 people with same gender be on the same boat to move to the opposite bank:

1move(X,Y,B) :- move1(X,Z,B,Gender), move1(Z,Y,B,Gender).

But that is not enough, this situation can still happen: Husband1 & Wife2 can be on left bank while Husband2 is on right bank. We have to put a constrain on this. A little convention here: Z is always initialized with 2, then it will hold the value of 0 or 1 depending on the recursive process.

- The wife is not with her husband on the bank Y:

1failcondition([[X,Y]|T],Z,H,W) :- X\=Y, (Z=Y;Z=2), W=0, failcondition(T,Y,H,1). - Another husband is also on that bank Y:

1failcondition([[Y,_]|T],Z,H,W) :- (Z=Y;Z=2), H=0, failcondition(T,Y,1,W). - The recursive process stops when it detects that there is a wife not being with her husband is on the same bank with other man:

1failcondition(_,_,1,1).

Maybe there is nothing wrong with the first couple, still we have to traverse through the list for the other couples:

1 |
failcondition([_|T],Z,H,W) :- failcondition(T,Z,H,W). |

And the state is valid if such thing does not happen:

1 |
condition(X) :- not(failcondition(X,2,0,0)). |

We have enough ingredients, the cooking part of f – the state transfer predicate should be easy:

1 |
f([BX|X],[BY|Y]) :- move(X,Y,BX), condition(Y), BY is 1-BX. |

Then comes the series of state space search predicates, I have an article about it here:

1 2 3 |
s(S,E,P) :- s1(S,E,[S],P1), reverse(P1,P). s1(E,E,R,R). s1(S,E,R,P) :- f(S,X), not(member(X,R)), s1(X,E,[X|R],P). |

Full program in Prolog:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
move2([[H,W]|T],[[H1,W1]|T],B) :- H=B, W=B, H1 is 1-H, W1 is 1-W. move2([X|T1],[X|T2],B) :- move2(T1,T2,B). move1([[H,W]|T],[[H1,W]|T],B,1) :- H=B, H1 is 1-H. move1([[H,W]|T],[[H,W1]|T],B,2) :- W=B, W1 is 1-W. move1([X|T1],[X|T2],B,Gender) :- move1(T1,T2,B,Gender). move(X,Y,B) :- move2(X,Y,B). move(X,Y,B) :- move1(X,Y,B,_). move(X,Y,B) :- move1(X,Z,B,Gender), move1(Z,Y,B,Gender). failcondition(_,_,1,1). failcondition([[X,Y]|T],Z,H,W) :- X\=Y, (Z=Y;Z=2), W=0, failcondition(T,Y,H,1). failcondition([[Y,_]|T],Z,H,W) :- (Z=Y;Z=2), H=0, failcondition(T,Y,1,W). failcondition([_|T],Z,H,W) :- failcondition(T,Z,H,W). condition(X) :- not(failcondition(X,2,0,0)). f([BX|X],[BY|Y]) :- move(X,Y,BX), condition(Y), BY is 1-BX. s(S,E,P) :- s1(S,E,[S],P1), reverse(P1,P). s1(E,E,R,R). s1(S,E,R,P) :- f(S,X), not(member(X,R)), s1(X,E,[X|R],P). |

Run the program:

1 |
s([0,[0,0],[0,0],[0,0]],[1,[1,1],[1,1],[1,1]],X). |

You may have realized that you can also try to solve this problem in size of n couples with this program. However, a friend of mine said that the version of this problem in size of four couples is unsolvable.

This is great, thank you so much!!! Very easy to follow and a great way to attack the problem.

I am trying to train my machine using this program to progressively find simpler and simpler solutions to this. As I understand it, the simplest solutions have 11 steps, and the results I am getting from this program get up to over 20 steps.

Any ideas or insight as to what queries to use or how to change the program to achieve this?

Thanks again so much!

It’s been a long time so I forgot how to use Prolog. I re-read what I wrote and I think *maybe* (I’m not sure) that you can get the shortest path by generating all solutions first. Maybe you can make a reference to the code block after the sentence “And maybe you want to count all the possible solution paths:” in this post. Hope it can help, though.

Thanks. Big fan of yours.