Задача о волке, козе и капусте¶

Задача о волке, козе и капусте — классическая логическая головоломка, относящаяся к классу задач на переправу (river crossing puzzles). В наиболее распространённой формулировке требуется перевезти через реку волка, козу и капусту, используя лодку, в которую помещается только один предмет (или животное) вместе с перевозчиком. Задача иллюстрирует принципы поиска в пространстве состояний, графов и планирования действий, а также часто используется в обучении основам алгоритмизации и искусственного интеллекта.

¶История и происхождение

Точное происхождение задачи неизвестно, но её корни восходят к средневековым европейским сборникам логических загадок. Впервые в письменном виде она встречается в трактате «Propositiones ad Acuendos Juvenes» («Задачи для оттачивания ума молодых»), приписываемом Алкуину Йоркскому (около 800 года н. э.). В этом сборнике, содержащем 56 логических задач, присутствует задача о волке, козе и капусте под номером 18. В оригинальной латинской версии фигурируют волк (lupus), коза (capra) и кочан капусты (caulis). Задача была широко распространена в фольклоре разных народов, часто с заменой персонажей: например, в русских вариантах могли фигурировать лиса, гусь и зерно, а в африканских — леопард, коза и бананы.

В эпоху Возрождения задача включалась в учебники по арифметике и логике. В XX веке она стала популярным примером в теории графов и информатике, а также в тестах на интеллект и собеседованиях.

¶Формулировка задачи

Классическая постановка задачи:

Крестьянин (или лодочник) стоит на левом берегу реки вместе с волком, козой и капустой.
Имеется лодка, в которой крестьянин может перевезти только один предмет (или животное) за один раз. Крестьянин должен переправляться сам, чтобы грести.
Нельзя оставлять без присмотра:
волка с козой (волк съест козу);
козу с капустой (коза съест капусту).
Волк с капустой остаются в безопасности друг без друга.
Требуется переправить всех троих на правый берег, соблюдая все ограничения.

¶Решение

Задача имеет единственное решение (с точностью до симметрии и порядка действий). Оно состоит из семи переправ (речных переходов) и включает возврат лодки на исходный берег.

¶Пошаговое решение

Перевезти козу на правый берег. На левом берегу остаются волк и капуста (они безопасны друг с другом). Лодка возвращается пустой (или с крестьянином) на левый берег.
Перевезти волка на правый берег. На правом берегу оказываются волк и коза — их нельзя оставлять вместе. Поэтому крестьянин забирает козу обратно на левый берег.
Оставить козу на левом берегу, перевезти капусту на правый берег. На правом берегу теперь волк и капуста (безопасны). Лодка возвращается пустой на левый берег.
Перевезти козу на правый берег. Все оказываются на правом берегу.

Альтернативный вариант: на втором шаге можно перевезти капусту, а затем вернуть козу, но логика остаётся той же.

¶Графическое представление

Состояние системы можно описать как кортеж (берег крестьянина, положение волка, козы, капусты). Решение в виде последовательности состояний (Л — левый берег, П — правый):

(Л, Л, Л, Л) — исходное.
(П, Л, П, Л) — коза на правом.
(Л, Л, П, Л) — лодка вернулась.
(П, П, П, Л) — волк на правом.
(Л, П, Л, Л) — коза вернулась.
(П, П, Л, П) — капуста на правом.
(Л, П, Л, П) — лодка вернулась.
(П, П, П, П) — коза на правом, все на месте.

¶Математическая модель и обобщения

Задача является частным случаем задачи о переправе с ограничениями. В терминах теории графов каждое состояние — вершина, а возможные переправы — рёбра. Решение представляет собой путь в графе от начального состояния к целевому. Количество состояний в классической задаче — 16 (2^4), но из-за ограничений допустимы только 10.

¶Обобщение на n объектов

Задача может быть обобщена на произвольное количество объектов с различными ограничениями. Например, задача о миссионерах и каннибалах, где требуется перевезти группу людей, не допуская, чтобы каннибалов оставалось больше, чем миссионеров. В общем виде задача о переправе с ограничениями является NP-полной при определённых условиях, но для малых размеров решается перебором.

¶Алгоритмические аспекты

В информатике задача используется для демонстрации:

поиска в ширину (BFS) — для нахождения кратчайшего пути;
поиска в глубину (DFS);
метода ветвей и границ;
логического программирования (Prolog, Answer Set Programming).

¶Применение в обучении и культуре

Задача о волке, козе и капусте широко применяется в педагогике и психологии:

Развитие логического мышления — у детей и взрослых.
Обучение программированию — как пример задачи на состояние и переходы.
Тестирование алгоритмов ИИ — в задачах планирования (например, в системе STRIPS).
В тестах на IQ — часто встречается в разделах на пространственное и логическое мышление.

В массовой культуре задача упоминается в книгах по занимательной математике (Я. Перельман, М. Гарднер), а также в эпизодах телесериалов (например, «Симпсоны», «Звёздный путь»). В русскоязычной среде она известна с детства как одна из «задач на смекалку».

¶Критика и ограничения

Задача критикуется за упрощённость и нереалистичность допущений: крестьянин не может оставить лодку без присмотра, животные и капуста ведут себя предсказуемо, а волк не нападает на человека. Однако именно эта абстракция делает задачу полезной для обучения основам логики и алгоритмов. В реальных сценариях (например, переправа скота) требуется учитывать множество дополнительных факторов (время, вместимость лодки, поведение животных).

¶Интересные факты

В некоторых версиях задачи вместо волка фигурирует лиса, а вместо капусты — гусь или зерно.
Задача имеет ровно одно решение (с точностью до симметрии), если не считать возвратов пустой лодки.
Минимальное количество переправ — 7 (включая возвраты).
В 1990-х годах задача была использована в качестве примера для демонстрации работы экспертных систем.
В 2012 году задача была включена в список «100 величайших головоломок всех времён» по версии журнала «New Scientist».

¶Источники

Алкуин Йоркский. «Propositiones ad Acuendos Juvenes» (ок. 800 г.).
Гарднер М. «Математические головоломки и развлечения». — М.: Мир, 1971.
Перельман Я. И. «Живая математика». — М.: Наука, 1967.
Russell S., Norvig P. «Artificial Intelligence: A Modern Approach» (3rd ed.). — Pearson, 2010.
New Scientist. «The 100 greatest puzzles of all time» (2012).

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →