River crossing puzzle

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.[1] The setting may vary cosmetically, for example, by replacing the river by a bridge.[1] The earliest known river-crossing problems occur in the manuscript Propositiones ad Acuendos Juvenes (English: 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.[2]

Well-known river-crossing puzzles include:

These problems may be analyzed using graph-theoretic methods,[4][5] by dynamic programming,[6] or by integer programming.[3]

References

  1. 1 2 Peterson, Ivars (2003), "Tricky crossings", Science News 164 (24), retrieved 2008-02-07.
  2. p. 74, Pressman, Ian; Singmaster, David (1989), ""The Jealous Husbands" and "The Missionaries and Cannibals"", The Mathematical Gazette (The Mathematical Association) 73 (464): 73–81, doi:10.2307/3619658, JSTOR 3619658.
  3. 1 2 Borndörfer, Ralf; Grötschel, Martin; Löbel, Andreas (1995), Alcuin's Transportation Problems and Integer Programming, Preprint SC-95-27, Konrad-Zuse-Zentrum für Informationstechnik Berlin.
  4. Schwartz, Benjamin L. (1961), "An analytic method for the "difficult crossing" puzzles", Mathematics Magazine 34 (4): 187–193, doi:10.2307/2687980, JSTOR 2687980.
  5. Csorba, Péter; Hurkens, Cor A. J.; Woeginger, Gerhard J. (2008), "The Alcuin number of a graph", Algorithms: ESA 2008, Lecture Notes in Computer Science 5193, Springer-Verlag, pp. 320–331, doi:10.1007/978-3-540-87744-8_27.
  6. Bellman, Richard (1962), "Dynamic programming and "difficult crossing" puzzles", Mathematics Magazine (Mathematical Association of America) 35 (1): 27–29, doi:10.2307/2689096, JSTOR 2689096.
This article is issued from Wikipedia - version of the Saturday, September 19, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.