Задача про вовка, козу і капусту

Задача про вовка, козу і капусту — логічна гра, яка ілюструє класичну проблему в області штучного інтелекту з пошуку рішення, яке задоволення системі обмежень.

З одного берега на іншій фермер має перевезти човном вовка, козу і капусту. Човен витримує лише човняра і одного «пасажира». Одночасно не можна залишати разом на березі вовка і козу, козу і капусту. Можна робити скільки завгодно рейсів.

Історія і варіації

Загадка є однією з низки головоломок про переправу, де об'єктом є набір елементів, а перехід через річку залежить від різних обмежень.

У самих ранніх відомих варіантах цієї проблеми, у середньовічному рукописі Propositiones ad Acuendos Juvenes, існують три об'єкти: вовк, коза і капуста. Також існують інші варіації головоломки, такі як лисиця, гусак і мішок зерна; вовк, вівця і капуста; лис, курка і хліб; лисиця, гусак і кукурудза;[1] fox, goose and corn[2] пантера, свиня, і каша. Логіка головоломки, в якій є три об'єкти, A, B, C і, такі, що ні А і В, ні B і C не можна залишити разом, залишається тією ж.

Головоломка була знайдена в фольклорі таких країн, як у Камерун, Кабо-Верде, Данія, Ефіопія, Гана, Італія, Румунія, Шотландія, Судан, Уганда, Замбія і Зімбабве. Головоломка отримала порядковий номер H506.3 у класифікації Томсона в категорії народної літературі, і АТО1579 в системі Аарне-Томпсона-Утера[3].

Загадка була фаворитом Льюїса Керролла, і була перевидана в різних колекціях рекреаційної математик[4].

В деяких частинах Африки були виявлені варіації на загадку, в яких судно може перевозити два об'єкти, а не тільки один. Коли головоломка ослаблена таким чином, то можна ввести додаткові обмеження, що немає двох елементів, у тому числі і С, котрих можна залишити разом.

Японська версія

Потрібно перевезти сім'ю з шести чоловік і поліцейського з бандитом на інший берег річки на плоту. Проте одночасно на пліт поміщаються тільки дві людини (Уточнення: один з яких повинен бути дорослим), мама, залишившись без тата, б'є хлопчиків, тато — дівчаток. А бандит (уточнення: за відсутності поліцейського) б'є всіх.

Розв'язок

Спочатку фермер перевозить козу (вовк капусти не з'їсть), а потім повертається і забирає вовка. Щоб вовк не з'їв кози, фермер забирає її і повертається за капустою. Залишивши козу, він перевозить капусту, а потім повертається по козу.

  1. перевезти козу туди;
  2. повернутися назад;
  3. перевезти капусту туди;
  4. перевезти козу назад;
  5. перевезти вовка туди;
  6. повернутися назад;
  7. перевезти козу туди;

Кроки 3) та 5) можна поміняти місцями.

Розв'язок у Lisp (пошук вшир)

 
 
(defun is_in (k lst)
  (cond
   ( (NULL lst) NIL)
   ( (eql k (car lst)) T)
   ( 1 (is_in k (cdr lst)) )
  )
)

(defun remove (k lst)
 (cond
  ((NULL lst) NIL)
  ((eql k (car lst)) (remove k (cdr lst)) )
  ( 1 (cons (car lst) (remove k (cdr lst))) )
 )
)

(defun is_ok (lst)
 (cond
  ( (NULL lst) T )
  ( (is_in 'man lst) T )
  ( (and (is_in 'goat lst) (is_in 'cabbage lst)) NIL)
  ( (and (is_in 'wolf lst) (is_in 'goat lst)) NIL)
  ( 1 T)
 )
)

(defun move (k)
 (cond
  ( (eql k 'man)
    (cond
     ((is_in 'man left) (setq left (remove 'man left)) (setq right (cons 'man right))? T)
     ((is_in 'man right) (setq right (remove 'man right)) (setq left (cons 'man left)) T)
    )
  )
  ( (and (is_in k left) (is_in 'man left)) (setq left (remove 'man (remove k left))) (setq right (cons 'man (cons k right))) T )
  ( (and (is_in k right) (is_in 'man right)) (setq right (remove 'man (remove k right))) (setq left (cons 'man (cons k left))) T )
  ( 1 NIL)
 )
)

(defun perevoz()
 (setq p (car way))
 (setq way (cdr way))

 (setq left (car (cdr p)))
 (setq right (car (cddr p)))
 (setq k (car p))
 (cond ((eql (length right) 4) (print p) (return)))
 (cond
   ( (and (is_ok left) (is_ok right))
     (cond ((and (neql (car(last k)) 'goat) (move 'goat)) (setq way (append way (list (list (append k (list 'goat)) left right)))) (move 'goat)))
     (cond ((and (neql (car(last k)) 'wolf) (move 'wolf)) (setq way (append way (list (list (append k (list 'wolf)) left right)))) (move 'wolf)))
     (cond ((and (neql (car(last k)) 'cabbage) (move 'cabbage)) (setq way (append way (list (list (append k (list 'cabbage)) left right))))(move 'cabbage)))
     (cond ((and (neql (car(last k)) 'man) (move 'man)) (setq way (append way (list (list (append k (list 'man)) left right))))(move 'man)))
   )
 )

 (perevoz)
)

(defun solve ()
   (setq way nil)
 
   (setq left '(goat cabbage wolf man))
   (setq right NIL)
   (move 'goat)
   (setq way (append way (list (list (list 'goat) left right))))

   (setq left '(goat cabbage wolf man))
   (setq right NIL)
   (move 'wolf)
   (setq way (append way (list (list (list 'wolf) left right))))
 
   (setq left '(goat cabbage wolf man))
   (setq right NIL)
   (move 'cabbage)
   (setq way (append way (list (list (list 'cabbage) left right))))

   (setq right NIL)
   (setq left NIL)

   (perevoz)
)

Див. також

Посилання
  1. The Classic River Crossing Puzzle. Архів оригіналу за 17 червня 2008. Процитовано 10 березня 2012.
  2. Mary Jane Sterling, Math Word Problems for Dummies, P.313
  3. «Carrying a Wolf, a Goat, and a Cabbage across the Stream. Metamorphoses of ATU 1579», Piret Voolaid, Folklore: Electronic Journal of Folklore 35 (2007), pp. 111—130. Tartu: Eesti Kirjandusmuuseum.
  4. p. 17, Rediscovered Lewis Carroll Puzzles, Lewis Carroll, compiled by Edward Wakeling, Courier Dover Publications, 1996, ISBN 0486288617
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.