Миссионеры и каннибалы

Условие: Три миссионера и три каннибала находятся на левом берегу реки.

Им нужно переправиться на правый берег на лодке, вмещающей не более двух человек.

Правило: На любом берегу каннибалов не должно быть больше миссионеров, если миссионеры там есть.

Ходов: 0
Левый берег
Лодка: на левом берегу
Правый берег

Как решить головоломку?

Минимальное число ходов — 11. Один из возможных путей:

  1. 2 каннибала →
  2. 1 каннибал ←
  3. 2 каннибала →
  4. 1 каннибал ←
  5. 2 миссионера →
  6. 1 миссионер + 1 каннибал ←
  7. 2 миссионера →
  8. 1 каннибал ←
  9. 2 каннибала →
  10. 1 каннибал ←
  11. 2 каннибала →

Ключевая идея: никогда не оставлять миссионеров в меньшинстве на любом берегу. Эта задача — классический пример поиска в пространстве состояний в искусственном интеллекте.