传教士和吃人恶魔问题

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

问题

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

解答

第一步、兩個惡魔過去: 结果此岸：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 種。

亦有將吃人惡魔以食人族代換的版本，不影響問題解法。

参见

狐狸、鹅、豆子问题