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).
Is there are way to know when a missionaries or cannibals problem has a solution or not (that is assuming that a solution means that no missionaries can be eaten and that boats can only carry two people)?
I have written a program that uses bfs to find possible solutions, and cannot seem to find a solution for 5 missionaries and 5 cannibals. It has worked for other missionaries and cannibals problems, so I'm not sure if my program is flawed or if there is just no solution. Its pretty obvious that in some situations (i.e. 1 missionary, 10 cannibals) there is no solution.
As a follow-up, would it be possible to shed some light on the situations in which missionaries must be eaten. Is there a way to find the minimum number of missionaries that can be eaten in a certain missionaries or cannibals problem?