O cão, o gato e o rato

Um homem tem um barco e quer atravessar o rio com um cão, um gato e um rato.
Alguns animais não podem ser deixados sozinhos na margem enquanto o homem rema:
O cão come o gato e o gato come o rato.
Além disso, ele só pode levar um animal de cada vez.