If there are , 8, missionaries , 3, cannibals , boat max. capacity, 2, and safety difference #missioanries-canniabls, 1 there are, 20, solutions Here they are {[[8, 3, 1], [6, 3, 0], [7, 3, 1], [5, 3, 0], [6, 3, 1], [4, 3, 0], [5, 3, 1], [5, 1, 0], [5, 2, 1], [3, 2, 0], [4, 2, 1], [4, 0, 0], [4, 1, 1], [2, 1, 0], [3 , 1, 1], [3, 0, 0], [4, 0, 1], [2, 0, 0], [2, 1, 1], [0, 1, 0], [0, 2, 1], [0, 0, 0]], [[8, 3, 1], [6, 3, 0], [7, 3, 1], [5, 3, 0], [6, 3, 1], [4, 3, 0], [5, 3, 1], [5, 1, 0], [5, 2, 1], [3, 2, 0], [4, 2, 1], [4, 0, 0], [4, 1, 1], [2, 1, 0], [3, 1, 1], [3, 0, 0], [4, 0, 1], [2, 0, 0], [3, 0, 1], [1, 0, 0], [2, 0, 1] , [0, 0, 0]], [[8, 3, 1], [6, 3, 0], [7, 3, 1], [5, 3, 0], [6, 3, 1], [4, 3, 0] , [5, 3, 1], [5, 1, 0], [5, 2, 1], [3, 2, 0], [4, 2, 1], [4, 0, 0], [4, 1, 1], [3, 1, 0], [3, 2, 1], [3, 0, 0], [4, 0, 1], [2, 0, 0], [2, 1, 1], [0, 1, 0], [0 , 2, 1], [0, 0, 0]], [[8, 3, 1], [6, 3, 0], [7, 3, 1], [5, 3, 0], [6, 3, 1], [4 , 3, 0], [5, 3, 1], [5, 1, 0], [5, 2, 1], [3, 2, 0], [4, 2, 1], [4, 0, 0], [4, 1, 1], [3, 1, 0], [3, 2, 1], [3, 0, 0], [4, 0, 1], [2, 0, 0], [3, 0, 1], [1, 0, 0], [2, 0, 1], [0, 0, 0]], [[8, 3, 1], [6, 3, 0], [7, 3, 1], [5, 3, 0], [6, 3, 1], [4, 3, 0], [5, 3, 1], [5, 1, 0], [5, 2, 1], [3, 2, 0], [4, 2, 1], [4, 1, 0] , [5, 1, 1], [3, 1, 0], [3, 2, 1], [3, 0, 0], [4, 0, 1], [2, 0, 0], [2, 1, 1], [0, 1, 0], [0, 2, 1], [0, 0, 0]], [[8, 3, 1], [6, 3, 0], [7, 3, 1], [5, 3, 0], [6, 3, 1], [4, 3, 0], [5, 3, 1], [5, 1, 0], [5, 2, 1], [3, 2, 0], [4, 2, 1], [4 , 1, 0], [5, 1, 1], [3, 1, 0], [3, 2, 1], [3, 0, 0], [4, 0, 1], [2, 0, 0], [3, 0, 1], [1, 0, 0], [2, 0, 1], [0, 0, 0]], [[8, 3, 1], [6, 3, 0], [7, 3, 1], [5, 3, 0], [6, 3, 1], [4, 3, 0], [5, 3, 1], [5, 1, 0], [5, 2, 1], [4, 2, 0], [4, 3, 1], [4, 1, 0], [5, 1, 1], [3, 1, 0], [3, 2, 1], [3, 0, 0], [4, 0, 1], [2, 0, 0] , [2, 1, 1], [0, 1, 0], [0, 2, 1], [0, 0, 0]], [[8, 3, 1], [6, 3, 0], [7, 3, 1] , [5, 3, 0], [6, 3, 1], [4, 3, 0], [5, 3, 1], [5, 1, 0], [5, 2, 1], [4, 2, 0], [4, 3, 1], [4, 1, 0], [5, 1, 1], [3, 1, 0], [3, 2, 1], [3, 0, 0], [4, 0, 1], [2 , 0, 0], [3, 0, 1], [1, 0, 0], [2, 0, 1], [0, 0, 0]], [[8, 3, 1], [6, 3, 0], [7 , 3, 1], [5, 3, 0], [6, 3, 1], [4, 3, 0], [5, 3, 1], [5, 2, 0], [6, 2, 1], [4, 2, 0], [4, 3, 1], [4, 1, 0], [5, 1, 1], [3, 1, 0], [3, 2, 1], [3, 0, 0], [4, 0, 1], [2, 0, 0], [2, 1, 1], [0, 1, 0], [0, 2, 1], [0, 0, 0]], [[8, 3, 1], [6, 3, 0], [7, 3, 1], [5, 3, 0], [6, 3, 1], [4, 3, 0], [5, 3, 1], [5, 2, 0], [6, 2, 1] , [4, 2, 0], [4, 3, 1], [4, 1, 0], [5, 1, 1], [3, 1, 0], [3, 2, 1], [3, 0, 0], [4, 0, 1], [2, 0, 0], [3, 0, 1], [1, 0, 0], [2, 0, 1], [0, 0, 0]], [[8, 3, 1], [8, 1, 0], [8, 2, 1], [6, 2, 0], [6, 3, 1], [4, 3, 0], [5, 3, 1], [5, 1, 0], [5 , 2, 1], [3, 2, 0], [4, 2, 1], [4, 0, 0], [4, 1, 1], [2, 1, 0], [3, 1, 1], [3, 0, 0], [4, 0, 1], [2, 0, 0], [2, 1, 1], [0, 1, 0], [0, 2, 1], [0, 0, 0]], [[8, 3, 1], [8, 1, 0], [8, 2, 1], [6, 2, 0], [6, 3, 1], [4, 3, 0], [5, 3, 1], [5, 1, 0], [5, 2, 1], [3, 2, 0], [4, 2, 1], [4, 0, 0], [4, 1, 1], [2, 1, 0], [3, 1, 1] , [3, 0, 0], [4, 0, 1], [2, 0, 0], [3, 0, 1], [1, 0, 0], [2, 0, 1], [0, 0, 0]], [[8, 3, 1], [8, 1, 0], [8, 2, 1], [6, 2, 0], [6, 3, 1], [4, 3, 0], [5, 3, 1], [ 5, 1, 0], [5, 2, 1], [3, 2, 0], [4, 2, 1], [4, 0, 0], [4, 1, 1], [3, 1, 0], [3, 2, 1], [3, 0, 0], [4, 0, 1], [2, 0, 0], [2, 1, 1], [0, 1, 0], [0, 2, 1], [0, 0, 0]], [[8, 3, 1], [8, 1, 0], [8, 2, 1], [6, 2, 0], [6, 3, 1], [4, 3, 0], [5, 3, 1], [5, 1, 0], [5, 2, 1], [3, 2, 0], [4, 2, 1], [4, 0, 0], [4, 1, 1], [3, 1, 0] , [3, 2, 1], [3, 0, 0], [4, 0, 1], [2, 0, 0], [3, 0, 1], [1, 0, 0], [2, 0, 1], [0, 0, 0]], [[8, 3, 1], [8, 1, 0], [8, 2, 1], [6, 2, 0], [6, 3, 1], [4, 3, 0], [5, 3, 1], [5, 1, 0], [5, 2, 1], [3, 2, 0], [4, 2, 1], [4, 1, 0], [5, 1, 1], [3 , 1, 0], [3, 2, 1], [3, 0, 0], [4, 0, 1], [2, 0, 0], [2, 1, 1], [0, 1, 0], [0, 2, 1], [0, 0, 0]], [[8, 3, 1], [8, 1, 0], [8, 2, 1], [6, 2, 0], [6, 3, 1], [4, 3, 0], [5, 3, 1], [5, 1, 0], [5, 2, 1], [3, 2, 0], [4, 2, 1], [4, 1, 0], [5, 1, 1], [3, 1, 0], [3, 2, 1], [3, 0, 0], [4, 0, 1], [2, 0, 0], [3, 0, 1], [1, 0, 0] , [2, 0, 1], [0, 0, 0]], [[8, 3, 1], [8, 1, 0], [8, 2, 1], [6, 2, 0], [6, 3, 1] , [4, 3, 0], [5, 3, 1], [5, 1, 0], [5, 2, 1], [4, 2, 0], [4, 3, 1], [4, 1, 0], [5, 1, 1], [3, 1, 0], [3, 2, 1], [3, 0, 0], [4, 0, 1], [2, 0, 0], [2, 1, 1], [0 , 1, 0], [0, 2, 1], [0, 0, 0]], [[8, 3, 1], [8, 1, 0], [8, 2, 1], [6, 2, 0], [6 , 3, 1], [4, 3, 0], [5, 3, 1], [5, 1, 0], [5, 2, 1], [4, 2, 0], [4, 3, 1], [4, 1, 0], [5, 1, 1], [3, 1, 0], [3, 2, 1], [3, 0, 0], [4, 0, 1], [2, 0, 0], [3, 0, 1], [1, 0, 0], [2, 0, 1], [0, 0, 0]], [[8, 3, 1], [8, 1, 0], [8, 2, 1], [6, 2, 0], [6, 3, 1], [4, 3, 0], [5, 3, 1], [5, 2, 0], [6, 2, 1], [4, 2, 0], [4, 3, 1] , [4, 1, 0], [5, 1, 1], [3, 1, 0], [3, 2, 1], [3, 0, 0], [4, 0, 1], [2, 0, 0], [2, 1, 1], [0, 1, 0], [0, 2, 1], [0, 0, 0]], [[8, 3, 1], [8, 1, 0], [8, 2, 1], [6, 2, 0], [6, 3, 1], [4, 3, 0], [5, 3, 1], [5, 2, 0], [6, 2, 1], [4, 2, 0], [4 , 3, 1], [4, 1, 0], [5, 1, 1], [3, 1, 0], [3, 2, 1], [3, 0, 0], [4, 0, 1], [2, 0, 0], [3, 0, 1], [1, 0, 0], [2, 0, 1], [0, 0, 0]]} Let's spell the first one Solution of a Missonaries and Cannibals River Crossing Problem 8, missionaries and , 3, cannibals have to cross a river using a rowboat that can have at most, 2, passengers At no time, on either bank of the river, and in the boat, should the excess \ of missionaries to cannibals be less than, 1, if there are any missionaries present, of course How to cross the river safely? Here is how to do it in, 10, double-crossings followed by one last crossing Right now the boat is at the Originating bank and there are, 8, missionaries and , 3, cannibals there while there are, 0, missionaries and , 0, canniabls on the other bank For the, 1, -th crossing from the Originating bank to the Terminal bank, put\ on the boat, 2, missionaries and , 0, cannibals Right now the boat is at the Terminating bank and there are, 2, missionaries and , 0, cannibals there while there are, 6, missionaries and , 3, canniabls on the other bank For the, 1, -th crossing from the Terminal bank back to the Originating bank\ , put on the boat, 1, missionaries and , 0, cannibals Right now the boat is at the Originating bank and there are, 7, missionaries and , 3, cannibals there while there are, 1, missionaries and , 0, canniabls on the other bank For the, 2, -th crossing from the Originating bank to the Terminal bank, put\ on the boat, 2, missionaries and , 0, cannibals Right now the boat is at the Terminating bank and there are, 3, missionaries and , 0, cannibals there while there are, 5, missionaries and , 3, canniabls on the other bank For the, 2, -th crossing from the Terminal bank back to the Originating bank\ , put on the boat, 1, missionaries and , 0, cannibals Right now the boat is at the Originating bank and there are, 6, missionaries and , 3, cannibals there while there are, 2, missionaries and , 0, canniabls on the other bank For the, 3, -th crossing from the Originating bank to the Terminal bank, put\ on the boat, 2, missionaries and , 0, cannibals Right now the boat is at the Terminating bank and there are, 4, missionaries and , 0, cannibals there while there are, 4, missionaries and , 3, canniabls on the other bank For the, 3, -th crossing from the Terminal bank back to the Originating bank\ , put on the boat, 1, missionaries and , 0, cannibals Right now the boat is at the Originating bank and there are, 5, missionaries and , 3, cannibals there while there are, 3, missionaries and , 0, canniabls on the other bank For the, 4, -th crossing from the Originating bank to the Terminal bank, put\ on the boat, 0, missionaries and , 2, cannibals Right now the boat is at the Terminating bank and there are, 3, missionaries and , 2, cannibals there while there are, 5, missionaries and , 1, canniabls on the other bank For the, 4, -th crossing from the Terminal bank back to the Originating bank\ , put on the boat, 0, missionaries and , 1, cannibals Right now the boat is at the Originating bank and there are, 5, missionaries and , 2, cannibals there while there are, 3, missionaries and , 1, canniabls on the other bank For the, 5, -th crossing from the Originating bank to the Terminal bank, put\ on the boat, 2, missionaries and , 0, cannibals Right now the boat is at the Terminating bank and there are, 5, missionaries and , 1, cannibals there while there are, 3, missionaries and , 2, canniabls on the other bank For the, 5, -th crossing from the Terminal bank back to the Originating bank\ , put on the boat, 1, missionaries and , 0, cannibals Right now the boat is at the Originating bank and there are, 4, missionaries and , 2, cannibals there while there are, 4, missionaries and , 1, canniabls on the other bank For the, 6, -th crossing from the Originating bank to the Terminal bank, put\ on the boat, 0, missionaries and , 2, cannibals Right now the boat is at the Terminating bank and there are, 4, missionaries and , 3, cannibals there while there are, 4, missionaries and , 0, canniabls on the other bank For the, 6, -th crossing from the Terminal bank back to the Originating bank\ , put on the boat, 0, missionaries and , 1, cannibals Right now the boat is at the Originating bank and there are, 4, missionaries and , 1, cannibals there while there are, 4, missionaries and , 2, canniabls on the other bank For the, 7, -th crossing from the Originating bank to the Terminal bank, put\ on the boat, 2, missionaries and , 0, cannibals Right now the boat is at the Terminating bank and there are, 6, missionaries and , 2, cannibals there while there are, 2, missionaries and , 1, canniabls on the other bank For the, 7, -th crossing from the Terminal bank back to the Originating bank\ , put on the boat, 1, missionaries and , 0, cannibals Right now the boat is at the Originating bank and there are, 3, missionaries and , 1, cannibals there while there are, 5, missionaries and , 2, canniabls on the other bank For the, 8, -th crossing from the Originating bank to the Terminal bank, put\ on the boat, 0, missionaries and , 1, cannibals Right now the boat is at the Terminating bank and there are, 5, missionaries and , 3, cannibals there while there are, 3, missionaries and , 0, canniabls on the other bank For the, 8, -th crossing from the Terminal bank back to the Originating bank\ , put on the boat, 1, missionaries and , 0, cannibals Right now the boat is at the Originating bank and there are, 4, missionaries and , 0, cannibals there while there are, 4, missionaries and , 3, canniabls on the other bank For the, 9, -th crossing from the Originating bank to the Terminal bank, put\ on the boat, 2, missionaries and , 0, cannibals Right now the boat is at the Terminating bank and there are, 6, missionaries and , 3, cannibals there while there are, 2, missionaries and , 0, canniabls on the other bank For the, 9, -th crossing from the Terminal bank back to the Originating bank\ , put on the boat, 0, missionaries and , 1, cannibals Right now the boat is at the Originating bank and there are, 2, missionaries and , 1, cannibals there while there are, 6, missionaries and , 2, canniabls on the other bank For the, 10, -th crossing from the Originating bank to the Terminal bank, pu\ t on the boat, 2, missionaries and , 0, cannibals Right now the boat is at the Terminating bank and there are, 8, missionaries and , 2, cannibals there while there are, 0, missionaries and , 1, canniabls on the other bank For the, 10, -th crossing from the Terminal bank back to the Originating ban\ k, put on the boat, 0, missionaries and , 1, cannibals Now the boat is at the Originating bank and there are, 0, missionaries and , 2, cannibals there while there are, 8, missionaries and , 1, canniabls on the other bank Finally for the , 11, -th crossing from the Original bank to the Terminal bank, put on the boat , 0, missionaries and , 2, cannibals Now everyone is in the Terminal bank ------------------------------------------------ This took, 0.073, seconds .