We can very easily design a simple Prolog program to perform depth first search - especially since Prolog uses depth first search itself.
We propose a predicate go/3 with two clauses which takes the current state and a goal state as its first and second arguments and returns the sequence of operators applied as the third argument (in the form of a list). The idea is to select some operator, check if it is worth applying, apply it and then check that the state is legal (i.e. no missionaries are eaten). Now recurse. Note that the recursion stops when the current state is the goal state.
Note that we are using backtracking to generate alternative operator selections which are then tested via the use of legal_state/1. This uses a Prolog programming technique termed generate and test.