传教士和吃人恶魔问题

传教士和吃人恶魔问题是一则古老的智力游戏题。

问题

有三个传教士和三个恶魔要渡过一条河，而河中有一条船，船只能容纳两个生物。而且在任何一个地方（无论是岸边还是船上），如果恶魔的数量多于传教士的数量，恶魔就会吃掉传教士。怎样才能让这些生物全都安全过河？（来回的船上都必须要有生物操作）

解答

过河问题解决方案的图

• 第一步、两个恶魔过去: 结果此岸：3 传教士，1 恶魔，彼岸：0 传教士 2 恶魔
• 第二步、一个恶魔回来；结果此岸：3 传教士，2 恶魔，彼岸：0 传教士 1 恶魔
• 第三步、两个恶魔过去；结果此岸：3 传教士，0 恶魔，彼岸：0 传教士 3 恶魔
• 第四步、一个恶魔回来；结果此岸：3 传教士，1 恶魔，彼岸：0 传教士 2 恶魔
• 第五步、两个传教过去；结果此岸：1 传教士，1 恶魔，彼岸：2 传教士 2 恶魔
• 第六步、一个传教士一个恶魔回来；结果此岸：2 传教士，2 恶魔，彼岸：1 传教士 1 恶魔
• 第七步、两个传教士过去；结果此岸：0 传教士，2 恶魔，彼岸：3 传教士 1 恶魔
• 第八步、一个恶魔回来；结果此岸：0 传教士，3 恶魔，彼岸：3 传教士 0 恶魔
• 第九步、两个恶魔过去；结果此岸：0 传教士，1 恶魔，彼岸：3 传教士 2 恶魔
• 第十步、一个恶魔回来；结果此岸：0 传教士，2 恶魔，彼岸：3 传教士 1 恶魔
• 第十一步、两个恶魔过去；结果此岸：0 传教士，0 恶魔，彼岸：3 传教士 3 恶魔

上面第一步可以有个变体：

• 第一步、一个传教士和一个恶魔过去: 结果此岸：2 传教士，2 恶魔，彼岸：1 传教士 1 恶魔
• 第二步、一个传教士回来；结果此岸：3 传教士，2 恶魔，彼岸：0 传教士 1 恶魔

上面第十步也可以有个变体：

• 第十步、一个传教士回来；结果此岸：1 传教士，1 恶魔，彼岸：2 传教士 2 恶魔
• 第十一步、一个传教士一个恶魔过去；结果此岸：0 传教士，0 恶魔，彼岸：3 传教士 3 恶魔

因此，对于三个传教士、三个恶魔的情况，共有 4 种不同的解法；

变体

如果船可以同时乘坐 2 位乘客时，传教士和恶魔都为 2 时，也有 4 种不同解法。但传教士和恶魔数都为 4 时没有解。 如果船可以同时乘坐 3 位乘客时，传教士和恶魔数都为 2，3，4，5时都有解法，其唯一解数分别为 12，54，72，216 种。 如果船可以同时乘坐 4 位乘客时，传教士和恶魔数为任意相同的数都有解法。比如 5 和 6 时，其唯一解数分别为 1200 和 3600 种。

亦有将吃人恶魔以食人族代换的版本，不影响问题解法。

参见

• 狐狸、鹅、豆子问题