River crossing puzzle
Encyclopedia
A river crossing puzzle is a type of transport puzzle
in which the object is to carry items from one river bank
to another. The difficulty of the puzzle may arise from restrictions on which or how many items can be transported at the same time, or from which or how many items may be safely left together. The setting may vary cosmetically, for example, by replacing the river by a bridge. The earliest known river-crossing problems occur in the manuscript Propositiones ad Acuendos Juvenes
(Problems to sharpen the young), traditionally said to be written by Alcuin
. The earliest copies of this manuscript date from the 9th century; it contains three river-crossing problems, including the fox, goose and bag of beans puzzle
and the jealous husbands problem.
Well-known river-crossing puzzles include:
These problems may be analyzed using graph-theoretic methods, by dynamic programming
, or by integer programming
.
Transport puzzle
Transport puzzles are logistical puzzles, which often represent real-life transport problems.-Description:In transport puzzles you move persons and/or objects through a given landscape. As in rearrangement puzzles, no piece is ever lost or added to the board...
in which the object is to carry items from one river bank
Stream bed
A stream bed is the channel bottom of a stream, river or creek; the physical confine of the normal water flow. The lateral confines or channel margins, during all but flood stage, are known as the stream banks or river banks. In fact, a flood occurs when a stream overflows its banks and flows onto...
to another. The difficulty of the puzzle may arise from restrictions on which or how many items can be transported at the same time, or from which or how many items may be safely left together. The setting may vary cosmetically, for example, by replacing the river by a bridge. The earliest known river-crossing problems occur in the manuscript Propositiones ad Acuendos Juvenes
Propositiones ad Acuendos Juvenes
The medieval Latin manuscript Propositiones ad Acuendos Juvenes is one of the earliest known collections of recreational mathematics problems. The oldest known copy of the manuscript dates from the late 9th century. The text is attributed to Alcuin of York Some editions of the text contain 53...
(Problems to sharpen the young), traditionally said to be written by Alcuin
Alcuin
Alcuin of York or Ealhwine, nicknamed Albinus or Flaccus was an English scholar, ecclesiastic, poet and teacher from York, Northumbria. He was born around 735 and became the student of Archbishop Ecgbert at York...
. The earliest copies of this manuscript date from the 9th century; it contains three river-crossing problems, including the fox, goose and bag of beans puzzle
Fox, goose and bag of beans puzzle
The fox, goose and bag of beans puzzle is a river-crossing puzzle. It dates back to at least the 9th century, and has entered the folklore of a number of ethnic groups.-The story:...
and the jealous husbands problem.
Well-known river-crossing puzzles include:
- The fox, goose and bag of beans puzzleFox, goose and bag of beans puzzleThe fox, goose and bag of beans puzzle is a river-crossing puzzle. It dates back to at least the 9th century, and has entered the folklore of a number of ethnic groups.-The story:...
, in which a farmer must transport a fox, goose and bag of beans from one side of a river to another using a boat which can only hold one item in addition to the farmer, subject to the constraints that the fox cannot be left alone with the goose, and the goose cannot be left alone with the beans. Equivalent puzzles have also been stated involving a fox, chicken, and bag of grain, or a wolf, goat, and cabbage, etc. - The jealous husbands problem, in which three married couples must cross a river using a boat which can hold at most two people, subject to the constraint that no woman can be in the presence of another man unless her husband is also present. This is similar to the missionaries and cannibals problemMissionaries and cannibals problemThe 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, where it was used by Saul Amarel as an example of problem...
, in which three missionaries and three cannibals must cross the river, with the constraint that at any time when both missionaries and cannibals are standing on either bank, the cannibals on that bank may not outnumber the missionaries. - The bridge and torch problemBridge and torch problemThe bridge and torch problem is a logic puzzle that deals with 4 people, a bridge and a torch. It is one of the category of river crossing puzzles, where a number of objects must move across a river, with some constraints.-Story:Four people come to a river in the night...
. - Propositio de viro et muliere ponderantibus plaustrum. In this problem, also occurring in Propositiones ad Acuendos Juvenes, a man and a woman of equal weight, together with two children, each of half their weight, wish to cross a river using a boat which can only carry the weight of one adult.
These problems may be analyzed using graph-theoretic methods, by dynamic programming
Dynamic programming
In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
, or by integer programming
Integer programming
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming, which is also known as mixed integer programming.Integer programming is NP-hard...
.