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.
