Yeah I'm thinking this one may be special cased, perhaps they wrote a generator of river crossing puzzles with corresponding conversion to "is_valid_state" or some such. I should see if I can get it to write something really ridiculous into "is_valid_state".
Other thing is that in real life its like "I need to move 12 golf carts, one has low battery, I probably can't tow more than 3 uphill, I can ask Bob to help but he will be grumpy...", just a tremendous amount of information (most of it irrelevant) with tremendous^tremendous^ possible moves (most of them possible to eliminate by actual thinking).