Couple problems and classic wolf/goat/cabbage and abstraction

Question

I was reviewing Dijkstra's approach on the problem/puzzle of how 2 married couple can cross a river with 1 boat that can carry 2 people. The original problem's restriction is that the wife can't be in the presence of another husband without hers being present as well.
His approach was to change the original restriction to be that the husbands have to stay together and the result of this abstraction is that there is no longer a need to distinguish between husband/wife so that the problem is simplified.
Although what he says is clear, I don't understand why the restriction is required in the first place.
The problem seems identical to the goat/cabbage/wolf where the cabbage and wolf had a symmetry with the goat (neither could be left alone with the goat) and hence replaced with an abstract concept "a".

Isn't this also applicable in the case of the couples? Is the approach of having an extra restriction redundant or not?

Answer 1

Of course if you can solve the problem with the husbands being apart at some point, that's just fine. That is, there is clearly no a priori need for imposing this additional restriction: the problem is stated the way it is ... why would you be required to add another restriction? That makes little sense.

Indeed, there is obviously a danger in trying to impose restrictions: maybe in doing so the problem actually becomes more difficult, if not impossible to solve. So, imposing further restrictions is not only unnecessary, but it could even be dangerous.

Now, one possible explanation for Dijkstra making this additional restriction is the following. Maybe Dijkstra analyzed the puzzle, and came to the conclusion that there is no solution possible if the husbands get separated. And note, depending on the nature of the puzzle, one can come to such a conclusion without actually finding all solutions to the puzzle, or even just a single one. And, if that is so, then yes, you might as well treat the two husbands as one item, thus eliminating the need to distinguish between the two, and treating them ,as you say, as one 'object' '$a$'.

Indeed, if you do treat the two husbands as one object '$a$', with the understanding that $a$ alone fills up the whole boat, it is easy to find a solution to this problem: Have the two wives row across, and have one of them return. Now send over '$a$', and have the second wive return, and finally have the two wives go across together again.

However, as others have pointed out, it turns out that there is also a solution with you keep the two husbands together: have one couple row across, after which the husband rows back to fetch the other husband, and then the wife rows back to fetch the other wife.

So, we know that the restriction that Dijkstra imposes is not necessitated at all. In fact, I would say Dijkstra was really rather 'lucky' in creating the additional restriction. How did he know that there was a solution where you could keep the two husbands together?

Answer 2

For completeness, here is a solution that does separate the two husbands. Let's say the couples are Mr. and Mrs. Smith and Mr. and Mrs. Jones:

1. The Smiths row across together.
2. Mr. Smith rows back.
3. Mr. Smith and Mr. Jones row across together.
4. Mrs. Smith rows back.
5. Mrs. Smith and Mrs. Jones row across together.

Dijkstra would very likely have hated it, but the most effective means we have for analysing protocols like this is informed trial and error (a.k.a. model checking). Model checking does often benefit from an intelligent choice of abstraction.