The missionaries and cannibals problem, and the closely related jealous husbands problem, are classic river-crossing logic puzzles. [1] 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 representation. [2] [3]
In the missionaries and cannibals problem, three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks, if there are missionaries present on the bank, they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries). The boat cannot cross the river by itself with no people on board. And, in some variations, one of the cannibals has only one arm and cannot row. [1]
In the jealous husbands problem, the missionaries and cannibals become three married couples, with the constraint that no woman can be in the presence of another man unless her husband is also present. Under this constraint, there cannot be both women and men present on a bank with women outnumbering men, since if there were, at least one such woman would be without her husband. Therefore, upon changing men to missionaries and women to cannibals, any solution to the jealous husbands problem will also become a solution to the missionaries and cannibals problem. [1]
A system for solving the Missionaries and Cannibals problem whereby the current state is represented by a simple vector ⟨m, c, b⟩. The vector's elements represent the number of missionaries, cannibals, and whether the boat is 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.
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. [4] , p. 291.
| 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. [4] , p. 291.
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. [5]
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 |
An obvious generalization is to vary the number of jealous couples (or missionaries and cannibals), the capacity of the boat, or both. If the boat holds 2 people, then 2 couples require 5 trips; with 4 or more couples, the problem has no solution. [6] If the boat can hold 3 people, then up to 5 couples can cross; if the boat can hold 4 people, any number of couples can cross. [4] , p. 300. A simple graph-theory approach to analyzing and solving these generalizations was given by Fraley, Cooke, and Detrick in 1966. [7]
If an island is added in the middle of the river, then any number of couples can cross using a two-person boat. If crossings from bank to bank are not allowed, then 8n−6 one-way trips are required to ferry n couples across the river; [1] , p. 76 if they are allowed, then 4n+1 trips are required if n exceeds 4, although a minimal solution requires only 16 trips if n equals 4. [1] , p. 79. If the jealous couples are replaced by missionaries and cannibals, the number of trips required does not change if crossings from bank to bank are not allowed; if they are however the number of trips decreases to 4n−1, assuming that n is at least 3. [1] , p. 81.
The first known appearance of the jealous husbands problem is in the medieval text Propositiones ad Acuendos Juvenes , usually attributed to Alcuin (died 804). In Alcuin's formulation the couples are brothers and sisters, but the constraint is still the same—no woman can be in the company of another man unless her brother is present. [1] , p. 74. From the 13th to the 15th century, the problem became known throughout Northern Europe, with the couples now being husbands and wives. [4] , pp. 291–293. The problem was later put in the form of masters and valets; the formulation with missionaries and cannibals did not appear until the end of the 19th century. [1] , p. 81 Varying the number of couples and the size of the boat was considered at the beginning of the 16th century. [4] , p. 296. Cadet de Fontenay considered placing an island in the middle of the river in 1879; this variant of the problem, with a two-person boat, was completely solved by Ian Pressman and David Singmaster in 1989. [1]
In 2020, controversy surrounding the racist themes in a cartoon about the problem led the AQA exam board to withdraw a text book containing the problem. [8]
The travelling salesman problem, also known as the travelling salesperson problem (TSP), asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.
Quadratic programming (QP) is the process of solving certain mathematical optimization problems involving quadratic functions. Specifically, one seeks to optimize a multivariate quadratic function subject to linear constraints on the variables. Quadratic programming is a type of nonlinear programming.
In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome in a mathematical model whose requirements and objective are represented by linear relationships. Linear programming is a special case of mathematical programming.
A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.
In computer science, local search is a heuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution that maximizes a criterion among a number of candidate solutions. Local search algorithms move from solution to solution in the space of candidate solutions by applying local changes, until a solution deemed optimal is found or a time bound is elapsed.
Branch and bound is a method for solving optimization problems by breaking them down into smaller sub-problems and using a bounding function to eliminate sub-problems that cannot contain the optimal solution. It is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.
The wolf, goat and cabbage problem is a river crossing puzzle. It dates back to at least the 9th century, and has entered the folklore of several cultures.
Route assignment, route choice, or traffic assignment concerns the selection of routes between origins and destinations in transportation networks. It is the fourth step in the conventional transportation forecasting model, following trip generation, trip distribution, and mode choice. The zonal interchange analysis of trip distribution provides origin-destination trip tables. Mode choice analysis tells which travelers will use which mode. To determine facility needs and costs and benefits, we need to know the number of travelers on each route and link of the network. We need to undertake traffic assignment. Suppose there is a network of highways and transit systems and a proposed addition. We first want to know the present pattern of traffic delay and then what would happen if the addition were made.
In mathematical optimization theory, the linear complementarity problem (LCP) arises frequently in computational mechanics and encompasses the well-known quadratic programming as a special case. It was proposed by Cottle and Dantzig in 1968.
A river crossing puzzle is a type of puzzle in which the object is to carry items from one river bank to another, usually in the fewest trips. The difficulty of the puzzle may arise from restrictions on which or how many items can be transported at the same time, or 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, 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.
Circumscription is a non-monotonic logic created by John McCarthy to formalize the common sense assumption that things are as expected unless otherwise specified. Circumscription was later used by McCarthy in an attempt to solve the frame problem. To implement circumscription in its initial formulation, McCarthy augmented first-order logic to allow the minimization of the extension of some predicates, where the extension of a predicate is the set of tuples of values the predicate is true on. This minimization is similar to the closed-world assumption that what is not known to be true is false.
God's algorithm is a notion originating in discussions of ways to solve the Rubik's Cube puzzle, but which can also be applied to other combinatorial puzzles and mathematical games. It refers to any algorithm which produces a solution having the fewest possible moves. The allusion to the deity is based on the notion that an omniscient being would know an optimal step from any given configuration.
The circulation problem and its variants are a generalisation of network flow problems, with the added constraint of a lower bound on edge flows, and with flow conservation also being required for the source and sink. In variants of the problem, there are multiple commodities flowing through the network, and a cost on the flow.
The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" It generalises the travelling salesman problem (TSP). It first appeared in a paper by George Dantzig and John Ramser in 1959, in which the first algorithmic approach was written and was applied to petrol deliveries. Often, the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. The objective of the VRP is to minimize the total route cost. In 1964, Clarke and Wright improved on Dantzig and Ramser's approach using an effective greedy algorithm called the savings algorithm.
The bridge and torch problem is a logic puzzle that deals with four people, a bridge and a torch. It is in the category of river crossing puzzles, where a number of objects must move across a river, with some constraints.
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, others 56. It has been translated into English by John Hadley, with annotations by John Hadley and David Singmaster.
The k shortest path routing problem is a generalization of the shortest path routing problem in a given network. It asks not only about a shortest path but also about next k−1 shortest paths. A variation of the problem is the loopless k shortest paths.
The problem of Multi-Agent Pathfinding (MAPF) is an instance of multi-agent planning and consists in the computation of collision-free paths for a group of agents from their location to an assigned target. It is an optimization problem, since the aim is to find those paths that optimize a given objective function, usually defined as the number of time steps until all agents reach their goal cells. MAPF is the multi-agent generalization of the pathfinding problem, and it is closely related to the shortest path problem in the context of graph theory.