A feladatnak összesen 4 megoldása van, ha eltekintünk a redundáns (ismétlődő lépésektől). (Ez visszalépéses kereséssel, irányított gráfreprezentációval, ...stb. könnyen látszik.)
Az egyes állapotokat számnégyesekkel jellemzem: az első szám a bal parton lévő misszionáriusok száma, a második a bal parton lévő kannibálok száma, a harmadik a jobb parton lévő misszionáriusok száma, míg a negyedik a jobb parton lévő kannibálok száma. Ezek után az egymást követő állapotok:
3300-(3102 vagy 2211)-3201-3003-3102-1122-2211-0231-0330-0132-(0231 vagy 1122)-0033