There are a few river crossing problems that I have seen that share some common aspects. The cannibal and missionary problem is typical. All these problems involve moving everyone from one side of the river to the other side by using a boat to cross the river. Denote by complement, an arrangement that is equivalent to what you get at any stage of the problem by swapping the shore that each person is at. For example, the final position of the puzzle is the complement of the initial position. One thing that these puzzles have in common is that it is legal to start at the final position and do the moves in reverse order and in the reverse direction, going from the final position to the initial position.
I noticed a relatively simple property of some of these problems that I am having trouble describing formally, let alone proving. In the solution to many of these problems there comes a point where a new position is the complement of the previous one. If you start at this position and perform the previous moves (except for the last) in reverse order, the last position will be the complement of the first, making the sequence of moves a solution. I hope that what I said makes sense. How could I state this in a more formal manner?
It should be pointed out that you can't actually do a complementation, but you can achieve the equivalent. For example, in the cannibal and misssonary problem, you go from having two cannibals and two missionaries on the far shore to having two cannibals and two missionaries on the near shore. This is done by having one cannibal and one missionary move from the far shore to the near shore, but could have also been achieved using complementation. I thought that the idea of complementation would simplify proofs.
Here is a more compact description. Let the positions be represented as (A,B), where A is the set of people on the near shore and B is the set of people on the far shore. The complement of (A,B) is (B,A). The starting position has the form (S,-) and the final position is (-,S).
If we have a sequence of moves (S,-)->...->(W,X)->(Y,Z) then we could perform the moves in reverse order, giving (Y,Z)->(W,X)...->(S,-). Suppose that you can go from (Y,Z) to its complement, (Y,Z)->(Z,Y). I would like to be able to show that we could go backwards (Z,Y)->(X,W)...->(-,S), giving a solution to the problem.
Here is an idea of what I would like to be able to say. In going from (W,X) to (Y,Z), the boat ends up on either the near shore or the far shore. In going from (Y,Z) to (Z,Y), the boat ends up on the opposite shore. This means that, in going backwards, it will be able to go from (Z,Y) to (X,W) and generate all the complements of the first set of reversed moves.