Общие DFS на речных кроссорах

Question

Я пытаюсь написать DFS, чтобы решить несколько проблем с перекресткой реки (капуста козья лиса, ревнивые мужья, наемники и каннибалы и т. Д.). Я написал классы головоломки, но у меня проблемы с структурированием моего решателя. Я понимаю, как работает DFS, но я не могу понять, с чего начать адаптировать его к этому дизайну.

Каждая головоломка имеет метод перемещения (), который возвращает истину, если это действительный ход, или ложь, если он нарушает набор правил. Пассажиры отслеживаются в паре списков, которые представляют каждую соответствующую сторону реки. У решателя есть доступ к этим спискам, но я не уверен, как использовать его для создания возможного набора хода, так как возможные движения будут меняться каждый раз, когда пассажир переживает через реку.

Answer 1

Создать validMoves Метод в вашем штате (или узле) объектах, которые возвращают массив, Collection или, что еще лучше, Iterator над движениями (или над действительными состояниями). Назовите это из алгоритма поиска (на этапе «расширения узла»).