General DFS on River Crossers

Question

I'm trying to write a DFS to solve multiple river crossing problems (Fox Goat Cabbage, Jealous Husbands, Mercenaries and Cannibals, etc.). I've written the puzzle classes, but I'm having trouble structuring my solver. I understand how DFS works, but I can't figure out where to start to adapt it to this design.

Each puzzle has a move() method which returns true if it's a valid move, or false if it breaks the ruleset. The passengers are tracked in a pair of lists which represent each respective side of the river. The solver has access to these lists, but I'm not sure how to use this to generate a possible move set, as the possible moves will change each time a passenger is taken across the river.

Answer 1

Create a validMoves method in your state (or node) objects that returns an array of, a Collection of, or, better yet, an Iterator over moves (or over valid states). Call this from the search algorithm (in the "node expansion" phase).