31:
78:
95:
126:, 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
46:
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.
316:
the bag of beans, then the two vertices would be connected since the goose cannot be left on the same side of the river with a bag of beans. Note that the edges are undirected, as the nature of the conflict between the two items does not affect the fact that they cannot be left on the same side of
141:, 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.
137:, 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
1003:
879:
691:
1254:
1127:
1189:
1062:
814:
469:
398:
160:, 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.
729:
1415:
1338:
923:
1444:
1367:
783:
592:
754:
539:
514:
367:
220:
314:
287:
1286:
632:
612:
563:
489:
438:
418:
339:
260:
240:
1292:. However, for certain classes of graphs, stronger results hold. For example, for planar graphs, determining which of the two relations holds can be done in
138:
123:
62:
317:
the river. The object of the problem is to determine the minimum size of the boat such that a trip is feasible; this is known as the
156:
49:
1559:
30:
61:. The earliest copies of this manuscript date from the 9th century; it contains three river-crossing problems, including the
127:
84:
928:
816:
items, they can be taken across the river one at a time in any order, occupying the one remaining space on the boat. Thus,
400:
items on the shore. Because the trip is successful, there must be no conflicts in the items left onshore; ie. in
145:
134:
101:
66:
819:
637:
1726:
1194:
1067:
1135:
1008:
785:, and thus leave one more space on the boat. Because there are no conflicts among any of the remaining
1621:
1261:
1555:
788:
443:
372:
173:
169:
77:
1667:
1647:
1597:
1533:
699:
1376:
1299:
884:
1420:
1343:
759:
568:
187:
1659:
1629:
1589:
1525:
1513:
1482:
292:
265:
1370:
1293:
1265:
165:
94:
1580:
Schwartz, Benjamin L. (1961), "An analytic method for the "difficult crossing" puzzles",
1628:, Lecture Notes in Computer Science, vol. 5193, Springer-Verlag, pp. 320–331,
734:
696:
On the other hand, it is possible to complete a successful trip with boat size equal to
519:
494:
347:
1565:
1564:, Preprint SC-95-27, Konrad-Zuse-Zentrum fĂĽr Informationstechnik Berlin, archived from
1478:
1271:
617:
597:
548:
474:
423:
403:
324:
245:
225:
1720:
17:
1455:
542:
1633:
756:
of a minimum vertex cover to remain on the boat at all times; these items number
1289:
1257:
344:
Consider a successful river crossing in which the farmer first carries a subset
1711:
1686:
43:
110:
1132:
Csorba, Hurkens, and
Woeginger proved in 2008 that determining which of
565:. Therefore, the size of the boat must be at least as large as the size
1671:
1601:
1537:
1516:(1989), ""The Jealous Husbands" and "The Missionaries and Cannibals"",
58:
1663:
1593:
1529:
262:
consists of pairs of items that conflict. For example, if a vertex
47:
The earliest known river-crossing problems occur in the manuscript
42:
is a type of puzzle in which the object is to carry items from one
29:
1650:(1962), "Dynamic programming and "difficult crossing" puzzles",
242:
represents items that the farmer must carry, and whose edge set
1268:, it follows that computing the Alcuin number of a graph
1561:
1423:
1379:
1346:
1302:
1274:
1197:
1138:
1070:
1011:
998:{\displaystyle \tau (G)\leq Alcuin(G)\leq \tau (G)+1}
931:
887:
822:
791:
762:
737:
702:
640:
620:
600:
571:
551:
522:
497:
477:
446:
426:
406:
375:
350:
327:
295:
268:
248:
228:
190:
152:
Propositio de viro et muliere ponderantibus plaustrum
614:; this forms a lower bound on the Alcuin number of
1688:River Crossings (and Alcuin Numbers) - Numberphile
1438:
1409:
1361:
1332:
1280:
1248:
1183:
1121:
1056:
997:
917:
873:
808:
777:
748:
723:
685:
626:
606:
586:
557:
533:
508:
483:
463:
432:
412:
392:
361:
333:
308:
281:
254:
234:
214:
1658:(1), Mathematical Association of America: 27–29,
1446:can both be computed exactly in polynomial time.
369:of items across the river, leaving the remaining
731:. This can be achieved by requiring the members
8:
1524:(464), The Mathematical Association: 73–81,
118:Well-known river-crossing puzzles include:
1422:
1378:
1345:
1301:
1273:
1196:
1137:
1069:
1010:
930:
886:
821:
790:
761:
736:
701:
639:
619:
599:
570:
550:
521:
496:
476:
445:
425:
405:
374:
349:
326:
300:
294:
273:
267:
247:
227:
189:
1624:(2008), "The Alcuin number of a graph",
874:{\displaystyle Alcuin(G)\leq \tau (G)+1}
222:be an undirected graph whose vertex set
1467:
795:
450:
379:
57:), traditionally said to be written by
686:{\displaystyle Alcuin(G)\geq \tau (G)}
154:. In this problem, also occurring in
164:These problems may be analyzed using
109:Solutions to some puzzles charted as
7:
1615:
1613:
1611:
1249:{\displaystyle Alcuin(G)=\tau (G)+1}
1122:{\displaystyle Alcuin(G)=\tau (G)+1}
925:. Combining these together, we have
1620:Csorba, PĂ©ter; Hurkens, Cor A. J.;
1549:
1547:
1473:
1471:
124:fox, goose, and bag of beans puzzle
63:fox, goose, and bag of beans puzzle
1184:{\displaystyle Alcuin(G)=\tau (G)}
1057:{\displaystyle Alcuin(G)=\tau (G)}
139:missionaries and cannibals problem
25:
157:Propositiones ad Acuendos Juvenes
50:Propositiones ad Acuendos Juvenes
93:
76:
594:of the minimum vertex cover of
1433:
1427:
1404:
1398:
1356:
1350:
1327:
1321:
1237:
1231:
1222:
1216:
1178:
1172:
1163:
1157:
1110:
1104:
1095:
1089:
1051:
1045:
1036:
1030:
986:
980:
971:
965:
941:
935:
912:
906:
862:
856:
847:
841:
772:
766:
712:
706:
680:
674:
665:
659:
581:
575:
471:. This implies that all edges
209:
197:
85:wolf, goat and cabbage problem
1:
881:, forming an upper bound for
809:{\displaystyle V\setminus V'}
491:have one or both vertices in
464:{\displaystyle V\setminus V'}
393:{\displaystyle V\setminus V'}
55:Problems to sharpen the young
1634:10.1007/978-3-540-87744-8_27
440:between any two elements of
1296:(though determining either
180:Graph theoretic formulation
1743:
1685:Numberphile (2018-01-05).
724:{\displaystyle \tau (G)+1}
1558:; Löbel, Andreas (1995),
1410:{\displaystyle Alcuin(G)}
1333:{\displaystyle Alcuin(G)}
918:{\displaystyle Alcuin(G)}
54:
1518:The Mathematical Gazette
1439:{\displaystyle \tau (G)}
1362:{\displaystyle \tau (G)}
778:{\displaystyle \tau (G)}
587:{\displaystyle \tau (G)}
420:, there are no edges in
146:bridge and torch problem
135:jealous husbands problem
102:bridge and torch problem
67:jealous husbands problem
289:represents a goose and
215:{\displaystyle G=(V,E)}
128:wolf, goat, and cabbage
34:Dog, sheep, and cabbage
1440:
1411:
1369:remains NP-hard); for
1363:
1334:
1282:
1250:
1185:
1123:
1058:
999:
919:
875:
810:
779:
750:
725:
687:
628:
608:
588:
559:
535:
510:
485:
465:
434:
414:
394:
363:
335:
310:
283:
256:
236:
216:
35:
27:Class of logic puzzles
1622:Woeginger, Gerhard J.
1441:
1412:
1364:
1335:
1283:
1251:
1186:
1124:
1059:
1000:
920:
876:
811:
780:
751:
726:
688:
629:
609:
589:
560:
536:
511:
486:
466:
435:
415:
395:
364:
336:
311:
309:{\displaystyle v_{2}}
284:
282:{\displaystyle v_{1}}
257:
237:
217:
40:river crossing puzzle
33:
18:River-crossing puzzle
1697:– via YouTube.
1652:Mathematics Magazine
1626:Algorithms: ESA 2008
1582:Mathematics Magazine
1421:
1377:
1344:
1300:
1272:
1262:minimum vertex cover
1195:
1136:
1068:
1009:
929:
885:
820:
789:
760:
735:
700:
638:
618:
598:
569:
549:
520:
495:
475:
444:
424:
404:
373:
348:
325:
293:
266:
246:
226:
188:
174:integer programming
170:dynamic programming
1554:Borndörfer, Ralf;
1483:"Tricky crossings"
1436:
1407:
1359:
1330:
1278:
1246:
1181:
1119:
1054:
995:
915:
871:
806:
775:
749:{\displaystyle V'}
746:
721:
683:
624:
604:
584:
555:
534:{\displaystyle V'}
531:
509:{\displaystyle V'}
506:
481:
461:
430:
410:
390:
362:{\displaystyle V'}
359:
331:
306:
279:
252:
232:
212:
36:
1556:Grötschel, Martin
1514:Singmaster, David
1281:{\displaystyle G}
627:{\displaystyle G}
607:{\displaystyle G}
558:{\displaystyle G}
484:{\displaystyle E}
433:{\displaystyle E}
413:{\displaystyle G}
334:{\displaystyle G}
255:{\displaystyle E}
235:{\displaystyle V}
16:(Redirected from
1734:
1699:
1698:
1696:
1695:
1682:
1676:
1674:
1648:Bellman, Richard
1644:
1638:
1636:
1617:
1606:
1604:
1577:
1571:
1569:
1551:
1542:
1540:
1508:
1502:
1500:
1499:
1498:
1475:
1445:
1443:
1442:
1437:
1416:
1414:
1413:
1408:
1371:bipartite graphs
1368:
1366:
1365:
1360:
1339:
1337:
1336:
1331:
1287:
1285:
1284:
1279:
1255:
1253:
1252:
1247:
1190:
1188:
1187:
1182:
1128:
1126:
1125:
1120:
1063:
1061:
1060:
1055:
1004:
1002:
1001:
996:
924:
922:
921:
916:
880:
878:
877:
872:
815:
813:
812:
807:
805:
784:
782:
781:
776:
755:
753:
752:
747:
745:
730:
728:
727:
722:
692:
690:
689:
684:
633:
631:
630:
625:
613:
611:
610:
605:
593:
591:
590:
585:
564:
562:
561:
556:
540:
538:
537:
532:
530:
515:
513:
512:
507:
505:
490:
488:
487:
482:
470:
468:
467:
462:
460:
439:
437:
436:
431:
419:
417:
416:
411:
399:
397:
396:
391:
389:
368:
366:
365:
360:
358:
340:
338:
337:
332:
315:
313:
312:
307:
305:
304:
288:
286:
285:
280:
278:
277:
261:
259:
258:
253:
241:
239:
238:
233:
221:
219:
218:
213:
97:
80:
56:
21:
1742:
1741:
1737:
1736:
1735:
1733:
1732:
1731:
1717:
1716:
1708:
1703:
1702:
1693:
1691:
1684:
1683:
1679:
1664:10.2307/2689096
1646:
1645:
1641:
1619:
1618:
1609:
1594:10.2307/2687980
1579:
1578:
1574:
1553:
1552:
1545:
1530:10.2307/3619658
1512:Pressman, Ian;
1511:
1509:
1505:
1496:
1494:
1479:Peterson, Ivars
1477:
1476:
1469:
1464:
1452:
1419:
1418:
1375:
1374:
1342:
1341:
1298:
1297:
1294:polynomial time
1270:
1269:
1193:
1192:
1134:
1133:
1066:
1065:
1007:
1006:
927:
926:
883:
882:
818:
817:
798:
787:
786:
758:
757:
738:
733:
732:
698:
697:
636:
635:
616:
615:
596:
595:
567:
566:
547:
546:
523:
518:
517:
498:
493:
492:
473:
472:
453:
442:
441:
422:
421:
402:
401:
382:
371:
370:
351:
346:
345:
323:
322:
296:
291:
290:
269:
264:
263:
244:
243:
224:
223:
186:
185:
182:
166:graph-theoretic
116:
115:
114:
113:
106:
105:
104:
98:
89:
88:
87:
81:
28:
23:
22:
15:
12:
11:
5:
1740:
1738:
1730:
1729:
1719:
1718:
1715:
1714:
1707:
1706:External links
1704:
1701:
1700:
1677:
1639:
1607:
1588:(4): 187–193,
1572:
1543:
1503:
1466:
1465:
1463:
1460:
1459:
1458:
1451:
1448:
1435:
1432:
1429:
1426:
1406:
1403:
1400:
1397:
1394:
1391:
1388:
1385:
1382:
1358:
1355:
1352:
1349:
1329:
1326:
1323:
1320:
1317:
1314:
1311:
1308:
1305:
1277:
1260:. Because the
1245:
1242:
1239:
1236:
1233:
1230:
1227:
1224:
1221:
1218:
1215:
1212:
1209:
1206:
1203:
1200:
1180:
1177:
1174:
1171:
1168:
1165:
1162:
1159:
1156:
1153:
1150:
1147:
1144:
1141:
1118:
1115:
1112:
1109:
1106:
1103:
1100:
1097:
1094:
1091:
1088:
1085:
1082:
1079:
1076:
1073:
1053:
1050:
1047:
1044:
1041:
1038:
1035:
1032:
1029:
1026:
1023:
1020:
1017:
1014:
994:
991:
988:
985:
982:
979:
976:
973:
970:
967:
964:
961:
958:
955:
952:
949:
946:
943:
940:
937:
934:
914:
911:
908:
905:
902:
899:
896:
893:
890:
870:
867:
864:
861:
858:
855:
852:
849:
846:
843:
840:
837:
834:
831:
828:
825:
804:
801:
797:
794:
774:
771:
768:
765:
744:
741:
720:
717:
714:
711:
708:
705:
682:
679:
676:
673:
670:
667:
664:
661:
658:
655:
652:
649:
646:
643:
623:
603:
583:
580:
577:
574:
554:
529:
526:
504:
501:
480:
459:
456:
452:
449:
429:
409:
388:
385:
381:
378:
357:
354:
330:
303:
299:
276:
272:
251:
231:
211:
208:
205:
202:
199:
196:
193:
181:
178:
162:
161:
149:
142:
131:
108:
107:
99:
92:
91:
90:
82:
75:
74:
73:
72:
71:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1739:
1728:
1727:Logic puzzles
1725:
1724:
1722:
1713:
1712:YouTube video
1710:
1709:
1705:
1690:
1689:
1681:
1678:
1673:
1669:
1665:
1661:
1657:
1653:
1649:
1643:
1640:
1635:
1631:
1627:
1623:
1616:
1614:
1612:
1608:
1603:
1599:
1595:
1591:
1587:
1583:
1576:
1573:
1568:on 2011-07-19
1567:
1563:
1562:
1557:
1550:
1548:
1544:
1539:
1535:
1531:
1527:
1523:
1519:
1515:
1507:
1504:
1492:
1488:
1484:
1480:
1474:
1472:
1468:
1461:
1457:
1454:
1453:
1449:
1447:
1430:
1424:
1401:
1395:
1392:
1389:
1386:
1383:
1380:
1372:
1353:
1347:
1324:
1318:
1315:
1312:
1309:
1306:
1303:
1295:
1291:
1275:
1267:
1263:
1259:
1243:
1240:
1234:
1228:
1225:
1219:
1213:
1210:
1207:
1204:
1201:
1198:
1175:
1169:
1166:
1160:
1154:
1151:
1148:
1145:
1142:
1139:
1130:
1116:
1113:
1107:
1101:
1098:
1092:
1086:
1083:
1080:
1077:
1074:
1071:
1048:
1042:
1039:
1033:
1027:
1024:
1021:
1018:
1015:
1012:
1005:, ie. either
992:
989:
983:
977:
974:
968:
962:
959:
956:
953:
950:
947:
944:
938:
932:
909:
903:
900:
897:
894:
891:
888:
868:
865:
859:
853:
850:
844:
838:
835:
832:
829:
826:
823:
802:
799:
792:
769:
763:
742:
739:
718:
715:
709:
703:
694:
677:
671:
668:
662:
656:
653:
650:
647:
644:
641:
621:
601:
578:
572:
552:
544:
527:
524:
502:
499:
478:
457:
454:
447:
427:
407:
386:
383:
376:
355:
352:
342:
328:
320:
319:Alcuin number
301:
297:
274:
270:
249:
229:
206:
203:
200:
194:
191:
179:
177:
175:
171:
167:
159:
158:
153:
150:
147:
143:
140:
136:
132:
129:
125:
121:
120:
119:
112:
103:
96:
86:
79:
70:
68:
64:
60:
52:
51:
45:
41:
32:
19:
1692:. Retrieved
1687:
1680:
1655:
1651:
1642:
1625:
1585:
1581:
1575:
1566:the original
1560:
1521:
1517:
1506:
1495:, retrieved
1490:
1487:Science News
1486:
1456:Vertex cover
1131:
695:
543:vertex cover
343:
318:
183:
168:methods, by
163:
155:
151:
117:
48:
39:
37:
1266:NP-complete
1264:problem is
516:, ie. that
1694:2024-05-17
1497:2008-02-07
1462:References
53:(English:
44:river bank
1425:τ
1348:τ
1256:holds is
1229:τ
1170:τ
1102:τ
1043:τ
978:τ
975:≤
945:≤
933:τ
854:τ
851:≤
796:∖
764:τ
704:τ
672:τ
669:≥
573:τ
451:∖
380:∖
111:timelines
1721:Category
1481:(2003),
1450:See also
803:′
743:′
528:′
503:′
458:′
387:′
356:′
172:, or by
65:and the
1672:2689096
1602:2687980
1538:3619658
1510:p. 74,
1290:NP-hard
1258:NP-hard
1670:
1600:
1536:
130:, etc.
59:Alcuin
1668:JSTOR
1598:JSTOR
1534:JSTOR
541:is a
1493:(24)
1417:and
184:Let
144:The
133:The
122:The
100:The
83:The
69:.
1660:doi
1630:doi
1590:doi
1526:doi
1491:164
1340:or
1288:is
1191:or
1064:or
545:of
341:.
321:of
1723::
1666:,
1656:35
1654:,
1610:^
1596:,
1586:34
1584:,
1546:^
1532:,
1522:73
1520:,
1489:,
1485:,
1470:^
1373:,
1129:.
693:.
634::
176:.
38:A
1675:.
1662::
1637:.
1632::
1605:.
1592::
1570:.
1541:.
1528::
1501:.
1434:)
1431:G
1428:(
1405:)
1402:G
1399:(
1396:n
1393:i
1390:u
1387:c
1384:l
1381:A
1357:)
1354:G
1351:(
1328:)
1325:G
1322:(
1319:n
1316:i
1313:u
1310:c
1307:l
1304:A
1276:G
1244:1
1241:+
1238:)
1235:G
1232:(
1226:=
1223:)
1220:G
1217:(
1214:n
1211:i
1208:u
1205:c
1202:l
1199:A
1179:)
1176:G
1173:(
1167:=
1164:)
1161:G
1158:(
1155:n
1152:i
1149:u
1146:c
1143:l
1140:A
1117:1
1114:+
1111:)
1108:G
1105:(
1099:=
1096:)
1093:G
1090:(
1087:n
1084:i
1081:u
1078:c
1075:l
1072:A
1052:)
1049:G
1046:(
1040:=
1037:)
1034:G
1031:(
1028:n
1025:i
1022:u
1019:c
1016:l
1013:A
993:1
990:+
987:)
984:G
981:(
972:)
969:G
966:(
963:n
960:i
957:u
954:c
951:l
948:A
942:)
939:G
936:(
913:)
910:G
907:(
904:n
901:i
898:u
895:c
892:l
889:A
869:1
866:+
863:)
860:G
857:(
848:)
845:G
842:(
839:n
836:i
833:u
830:c
827:l
824:A
800:V
793:V
773:)
770:G
767:(
740:V
719:1
716:+
713:)
710:G
707:(
681:)
678:G
675:(
666:)
663:G
660:(
657:n
654:i
651:u
648:c
645:l
642:A
622:G
602:G
582:)
579:G
576:(
553:G
525:V
500:V
479:E
455:V
448:V
428:E
408:G
384:V
377:V
353:V
329:G
302:2
298:v
275:1
271:v
250:E
230:V
210:)
207:E
204:,
201:V
198:(
195:=
192:G
148:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
