Ответ в теме: Поиск в глубину в задаче про пять супружеских пар

      Комментарии к записи Ответ в теме: Поиск в глубину в задаче про пять супружеских пар отключены
#1879

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

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