Existem 3 cachorros e 3 gatos que precisam atravessar uma rua. O número de gatos de um dos lados da rua nunca deve ser inferior ao número de cachorros naquele mesmo lado, ou serão devorados. Todos os animais devem finalizar a travessia para o outro lado sem que nenhum gato seja devorado.


Regras:

- O número máximo de animais que pode atravessar a rua é de dois animais por vez;

- Não é possível a travessia de dois animais, simultaneamente, em direções contrárias;

- Um gato pode atravessar a rua com um cachorro (desde que seja na mesma direção);

- Sempre que ocorrer uma travessia em uma direção, a outra deve obrigatoriamente ocorrer na direção oposta;

Ex: se a última travessia ocorreu da esquerda para a direita, a próxima deve ocorrer obrigatoriamente da direita para a esquerda.
- Todos os animais podem ir e voltar quantas vezes forem necessárias.



Objetivo: elaborar a sequência correta de passos para resolver o problema.​