canibais e missionarios

Problema dos canibais e dos missionários
Três canibais e três missionários estão viajando juntos e chegam à margem de um rio. Eles desejam atravessar para a outra margem para, desta forma, continuar a viagem. O único meio de transporte disponível é um barco que comporta no máximo duas pessoas. Há uma outra dificuldade: em nenhum momento o número de canibais pode ser superior ao número de missionários pois desta forma os missionários estariam em grande perigo de vida. Como administrar a travessia?
Para resolver este problema, considere as situações (ou estados) no que se refere ao número de canibais e missionários que estão numa das duas margens, sempre considerando que o barco está aportado, ou seja, antes do início de uma travessia ou quando ela foi completada. Podemos representar cada um destes estados por uma tripla de valores (c,m,b), onde c e m representam o número de canibais e de missionários, respectivamente, que estão na margem b onde está o barco.
Uma tripla como (2, 2, esquerda) significa que temos dois canibais e dois missionários na margem esquerda, e que o barco está nesta margem. Apesar de não estar explicitamente dito, é fácil saber que neste instante temos 1 canibal e 1 missionário na margem direita (complemento em relação ao par (3,3)).

Um modelo para este problema é dado, então, pelo grafo G(V,A):
V = { (c,m,b) | c e m representam o número de canibais e de missionários na margem b do rio, estando o barco nesta margem}
A = { (ex,ey) | ex = (cx,mx,bx) é o estado na margem onde o barco está antes da travessia ser iniciada, e ey = (cy,my,by) é o estado na margem oposta após o barco completar a travessia}
Como o barco comporta no máximo 2 pessoas, há 5 possíveis situações quanto aos passageiros do barco em cada travessia:
1 canibal;
2 canibais;
1 missionário;
2 missionários;
1 canibal e 1 missionário.
A tabela que se segue descreve as restrições par que uma travessia possa ocorrer, considerando x e y com sendo as margens