Three Wives & Their Jealous Husbands
Three jealous husbands with their wives, having to cross a river, find a boat without a boatman. But the boat is so small that it can contain no more than two of them at a time.
How can these six persons cross the river so that none of the women shall be left in the company of any of the men unless her husband is present?
(Women to row when absolutely necessary to prevent a violation of the above conditions).
Let the three husbands be A,B and C and their wives a,b and c respectively. The following moves are typical of a minimum solution with men rowing where possible.
Left Bank | Crossing | Right Bank |
ABCabc | – | – |
ACac | Bb ® | – |
ACac | ¬ B | b |
ABC | ac ® | b |
ABC | ¬ a | bc |
Aa | BC ® | bc |
Aa | ¬ Bb | Cc |
ab | AB ® | Cc |
ab | ¬ c | ABC |
b | ac ® | ABC |
b | ¬ B | ACac |
– | Bb® | ACac |
– | – | ABCabc |
Note that only a, B, and c need be able to row.
The missionaries and cannibals problem, and the closely related jealous husbands problem, are classic river-crossing problems
The missionaries and cannibals problem is a well-known toy problem in artificial intelligence
Source of solution – WIKIPEDIA
Solving-
Amarel devised a system for solving the Missionaries and Cannibals problem whereby the current state is represented by a simple vector <a,b,c>. The vector’s elements represent the number of missionaries on the wrong side, the number of cannibals on the wrong side, and the number of boats on the wrong side, respectively. Since the boat and all of the missionaries and cannibals start on the wrong side, the vector is initialized to <3,3,1>. Actions are represented using vector subtraction/addition to manipulate the state vector. For instance, if a lone cannibal crossed the river, the vector <0,1,1> would be subtracted from the state to yield <3,2,0>. The state would reflect that there are still three missionaries and two cannibals on the wrong side, and that the boat is now on the opposite bank. To fully solve the problem, a simple tree is formed with the initial state as the root. The five possible actions (<1,0,1>, <2,0,1>, <0,1,1>, <0,2,1>, and <1,1,1>) are then subtracted from the initial state, with the result forming children nodes of the root. Any node that has more cannibals than missionaries on either bank is in an invalid state, and is therefore removed from further consideration. The valid children nodes generated would be <3,2,0>, <3,1,0>, and <2,2,0>. For each of these remaining nodes, children nodes are generated by adding each of the possible action vectors. The algorithm continues alternating subtraction and addition for each level of the tree until a node is generated with the vector <0,0,0> as its value. This is the goal state, and the path from the root of the tree to this node represents a sequence of actions that solves the problem.
SOLUTION–
The earliest solution known to the jealous husbands problem, using 11 one-way trips, is as follows. The married couples are represented as (male) and a (female), and b, and and c.
Trip number | Starting bank | Travel | Ending bank |
---|---|---|---|
(start) | a b c | ||
1 | b c | a → | |
2 | b c | ← | a |
3 | bc → | a | |
4 | ← a | b c | |
5 | a | → | b c |
6 | a | ← b | c |
7 | a b | → | c |
8 | a b | ← c | |
9 | b | a c → | |
10 | b | ← | a c |
11 | b → | a c | |
(finish) | a b c |
This is a shortest solution to the problem, but is not the only shortest solution
If however, only one man can get out of the boat at a time and husbands must be on the shore to count as with his wife as opposed to just being in the boat at the shore: move 5 to 6 is impossible, for as soon as has stepped out b on the shore won’t be with her husband, despite him being just in the boat.
As mentioned previously, this solution to the jealous husbands problem will become a solution to the missionaries and cannibals problem upon replacing men by missionaries and women by cannibals. In this case we may neglect the individual identities of the missionaries and cannibals. The solution just given is still shortest, and is one of four shortest solutions.
If a woman in the boat at the shore (but not on the shore) counts as being by herself (i.e. not in the presence of any men on the shore), then this puzzle can be solved in 9 one-way trips:
Trip number | Starting bank | Travel | Ending bank |
---|---|---|---|
(start) | a b c | ||
1 | b c | a → | |
2 | b c | ← a | |
3 | c | ab → | |
4 | c | ← b | a |
5 | c | b → | a |
6 | c | ← b | a |
7 | bc → | a | |
8 | ← c | a b | |
9 | c → | a b | |
(finish) | a b c |
Your Answer
More puzzles to try-
Crazy Riddle
Why is it against the law for a man living in Delhi to be buried in Mumbai?Read More »Find the number
Find the next number if the sequence if you can 102 104 108 110 114 128 ?Read More »Identify the Rebus
What does this rebus picture identify?Read More »25 horses 5 tracks Puzzle
Mr John have 25 horses, and he want to pick the fastest 3 horses out of those 25. He has only ...Read More »How Many Sweets?
Sally and Anna bought 8 sweets and shared between themselves. Sally ate 2 more sweets than Anna did. How many ...Read More »who follow you
Who always follow you during the day but becomes too tired to follow you at night?Read More »Voiceless but cries riddle
Voiceless it cries, Wingless flutters, Toothless bites, Mouth-less mutters. Who is this?Read More »Continuous moving buses puzzle
A bus route has a total duration of 40 minutes. Every 10 minutes, two buses set out, one from each ...Read More »Do they look straight or curved to you?
This optical illusion was first created in 1861. Look at the two thick vertical lines. Do they look straight or ...Read More »Time and Work
19 persons do 19 programs in 19 hours . If they take 15 mins interval and then how much time ...Read More »What am I?
I am a 12 letter word Letters 1 to 4 mean shout at the top of your voice! Letters 7 ...Read More »Programmers puzzle
What will be the output of the program- print(5);Read More »Word Change Riddle
Can you transform the word THINK into BRAIN while changing only one letter at a time in a manner that ...Read More »Car Wheel Rotation
Which wheel of car does not rotate when you turn your car right?Read More »Shortest complete sentence
I am the shortest complete sentence in the English language. What am I?Read More »Animals in a Zoo
If a zookeeper had 100 pairs of animals in her zoo, and two pairs of babies are born for each ...Read More »Decode
In a certain code if DESTINED is written as UTFECDMH, then how would you write QUESTION?Read More »The Word Ladder
Can you transform each of the top words into the word on the bottom? You can only change one letter ...Read More »Dog Crosses River Riddle
A man calls his dog from the opposite side of a river. The dog crosses the river without a bridge ...Read More »How many days riddle
How many days are there in 4 years?Read More »