Prolog — задача 79 кто украл сковороду

  • В этой теме 0 ответов, 1 участник, последнее обновление 1 неделя, 6 дней назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6775
      @admin

      Задача:

      Кто украл сковороду?
      — Вот еще немного соли,—сказал Король.— Теперь-то ты можешь испечь кренделей?
      — Не могу,— ответила Королева,— Кто-то украл мою сковороду.
      — Сковороду!—вскричал в ярости Король.—Что ж, разыщем и ее!
      На этот раз в число подозреваемых попали Лягушонок, Лакей-Лещ и Валет Червей. На суде они заявили следующее:
      Лягушонок. Сковороду украл Лакей-Лещ.
      Лакей-Лещ. Ваше Величество, не крал я никакой сковороды.
      Валет Червей. Я украл сковороду!
      — Какой помощник правосудия выискался!— закричал Король на Валета Червей.—Рта не можешь раскрыть, чтобы не солгать!
      Выяснилось, что не более чем один подсудимый лгал.
      Кто украл сковороду?

      Приведенные тут варианты решения очень легко читаются — я думаю, к ним не нужны дополнительные пояснения. Если что-то не понятно — спрашивайте. Наиболее сложные предикаты — входит_в, без_повторов и убрать_повторы подробно разобраны тут. Там же, объясняется как понять findall. Также, понять решение может помочь статья «Решение логических задач на Prolog«.

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

      Решение 1

      DOMAINS 
      	подозреваемый = leg; lak; val
      	гипотеза = вор(подозреваемый)
      	
      	подозреваемые = подозреваемый*
      PREDICATES      
             nondeterm возможный_вор(подозреваемый)
             nondeterm генерация_гипотезы(гипотеза)
             
             nondeterm проверка_гипотезы(гипотеза)
             
             nondeterm сказал_правду(подозреваемый, гипотеза)
             nondeterm солгал(подозреваемый, гипотеза)
             
             nondeterm проверка_лжецов(подозреваемые)
             
      CLAUSES 
      	возможный_вор(leg).
      	возможный_вор(lak).
      	возможный_вор(val).
      	
      	генерация_гипотезы(вор(Вор)):-
      		возможный_вор(Вор).
      		
      	сказал_правду(leg, вор(lak)).
      	сказал_правду(lak, вор(Вор)):-
      		NOT(Вор = lak).
      	сказал_правду(val, вор(val)).
      	
      	солгал(Кто, Гипотеза):-
      		возможный_вор(Кто),
      		NOT(сказал_правду(Кто, Гипотеза)).
      		
      	% проверяет что солгал не более чем один
      	проверка_лжецов([]). % никто не солгал
      	проверка_лжецов([_]). % один солгал
      		
      	проверка_гипотезы(Гипотеза):-
      		Гипотеза = вор(Вор),
      		findall(Солгал, солгал(Солгал, вор(Вор)), Солгали),
      		проверка_лжецов(Солгали).
      GOAL    
             /* 
      	генерация_гипотезы(Гипотеза),
      	Гипотеза = вор(Вор),
      	findall(Солгал, солгал(Солгал, вор(Вор)), Солгали).
      	*/
      	
              генерация_гипотезы(Гипотеза),
              проверка_гипотезы(Гипотеза).
      

      Решение 2

      DOMAINS 
      	имя = лягушенок; лакей; валет
      	роль = вор;не_вор
      	персонаж = персонаж(имя, роль)
      	
      	гипотеза = персонаж*
      	имена = имя*
      PREDICATES      
             nondeterm возможный_вор(имя)
             nondeterm возможная_роль(роль)
             nondeterm генерация_гипотезы(гипотеза)
             
             nondeterm проверка_гипотезы(гипотеза)
             
             nondeterm сказал(имя, гипотеза)
             nondeterm солгал(имя, гипотеза)
             
             nondeterm не_более_чем_один(имена)
             nondeterm только_один(имена)
             
             nondeterm входит_в(персонаж, гипотеза)
             
      CLAUSES 
      	возможный_вор(лягушенок).
      	возможный_вор(лакей).
      	возможный_вор(валет).
      	
      	возможная_роль(вор).
      	возможная_роль(не_вор).
      	
      	генерация_гипотезы([
      		персонаж(лягушенок, РольЛягушенка),
      		персонаж(лакей, РольЛакея),
      		персонаж(валет, РольВалета)
      	]):-
      		возможная_роль(РольЛягушенка), 
      		возможная_роль(РольЛакея), 
      		возможная_роль(РольВалета).
      		
      	сказал(лягушенок, Гипотеза):-
      		входит_в(персонаж(лакей, вор), Гипотеза).
      	сказал(лакей, Гипотеза):-
      		входит_в(персонаж(лакей, РольЛакея), Гипотеза),
      		NOT(РольЛакея = вор).
      	сказал(валет, Гипотеза):-
      		входит_в(персонаж(валет, вор), Гипотеза).
      	
      	солгал(Кто, Гипотеза):-
      		возможный_вор(Кто),
      		NOT(сказал(Кто, Гипотеза)).
      		
      	не_более_чем_один([]). 
      	не_более_чем_один([_]).
      	
      	только_один([_]).
      	
      	входит_в(Элемент, [Элемент|_ОстальныеЭлементы]).
      	входит_в(Элемент, [_ПервыйЭлемент|ОстальныеЭлементы]):-
      		входит_в(Элемент, ОстальныеЭлементы).
      	
      	проверка_гипотезы(Гипотеза):-
      		% только один вор:
      		findall(Вор, входит_в(персонаж(Вор, вор), Гипотеза), Воры),
      		только_один(Воры),
      		
      		% не более чем один лгал
      		findall(Лжец, солгал(Лжец, Гипотеза), Лжецы),
      		не_более_чем_один(Лжецы).
      		
      		
      GOAL    
              генерация_гипотезы(Гипотеза),
              проверка_гипотезы(Гипотеза).
      

      Решение 3

      DOMAINS 
      	имя = лягушенок; лакей; валет
      	роль = вор;не_вор
      	персонаж = персонаж(имя, роль, истинность)
      	истинность = правда;ложь
      	
      	гипотеза = персонаж*
      	имена = имя*
      PREDICATES      
             nondeterm возможный_вор(имя)
             nondeterm возможная_роль(роль)
             nondeterm возможная_истинность(истинность)
                
             nondeterm генерация_гипотезы(гипотеза)
             nondeterm проверка_гипотезы(гипотеза)
             
             nondeterm сказал(имя, гипотеза)
             nondeterm солгал(имя, гипотеза)
             
             nondeterm проверка_высказывания(имя, гипотеза)
             
             nondeterm не_более_чем_один(имена)
             nondeterm только_один(имена)
             
             nondeterm входит_в(персонаж, гипотеза)
             
      CLAUSES 
      	возможный_вор(лягушенок).
      	возможный_вор(лакей).
      	возможный_вор(валет).
      	
      	возможная_роль(вор).
      	возможная_роль(не_вор).
      	
             возможная_истинность(правда).
             возможная_истинность(ложь).
      	
      	генерация_гипотезы([
      		персонаж(лягушенок, РольЛягушенка, ИстинностьЛягушенка),
      		персонаж(лакей, РольЛакея, ИстинностьЛакея),
      		персонаж(валет, РольВалета, ИстинностьВальта)
      	]):-
      		возможная_роль(РольЛягушенка), 
      		возможная_роль(РольЛакея), 
      		возможная_роль(РольВалета),
      		
      		возможная_истинность(ИстинностьЛягушенка),
      		возможная_истинность(ИстинностьЛакея),
      		возможная_истинность(ИстинностьВальта).
      		
      	сказал(лягушенок, Гипотеза):-
      		входит_в(персонаж(лакей, вор,_ИстинностьЛакея), Гипотеза).
      	сказал(лакей, Гипотеза):-
      		входит_в(персонаж(лакей, РольЛакея,_ИстинностьЛакея), Гипотеза),
      		NOT(РольЛакея = вор).
      	сказал(валет, Гипотеза):-
      		входит_в(персонаж(валет, вор,_ИстинностьВальта), Гипотеза).
      
      	солгал(Кто, Гипотеза):-
      		возможный_вор(Кто),
      		NOT(сказал(Кто, Гипотеза)).
      		
      	проверка_высказывания(Кто, Гипотеза):-
      		входит_в(персонаж(Кто, _Роль, правда), Гипотеза),
      		сказал(Кто, Гипотеза);
      		
      		входит_в(персонаж(Кто, _Роль, ложь), Гипотеза),
      		солгал(Кто, Гипотеза).
      		
      	не_более_чем_один([]). 
      	не_более_чем_один([_]).
      	
      	только_один([_]).
      	
      	входит_в(Элемент, [Элемент|_ОстальныеЭлементы]).
      	входит_в(Элемент, [_ПервыйЭлемент|ОстальныеЭлементы]):-
      		входит_в(Элемент, ОстальныеЭлементы).
      	
      	проверка_гипотезы(Гипотеза):-
      		% только один вор:
      		findall(Вор, входит_в(персонаж(Вор, вор,_ИстинностьВора), Гипотеза), Воры),
      		только_один(Воры),
      		
      		% не более чем один лгал
      		findall(Лжец, солгал(Лжец, Гипотеза), Лжецы),
      		не_более_чем_один(Лжецы),
      		
      		проверка_высказывания(лягушенок, Гипотеза),
      		проверка_высказывания(лакей, Гипотеза),
      		проверка_высказывания(валет, Гипотеза).
      		
      		
      GOAL    
              генерация_гипотезы(Гипотеза),
              проверка_гипотезы(Гипотеза).
      

      Решение 4

      DOMAINS 
      	имя = лЯгушенок; лакей; валет
      	роль = вор;не_вор
      	персонаж = персонаж(имя, роль, истинность)
      	истинность = правда;ложь
      	
      	гипотеза = персонаж*
      	имена = имя*
      PREDICATES      
             nondeterm возможный_вор(имя)
             nondeterm возможная_роль(роль)
             nondeterm возможная_истинность(истинность)
                
             nondeterm генерация_гипотезы(гипотеза)
             nondeterm проверка_гипотезы(гипотеза)
             
             nondeterm сказал(имя, гипотеза)
             
             nondeterm проверка_высказывания(имя, гипотеза)
             
             nondeterm сколько_солгали(гипотеза, integer)
             
             nondeterm входит_в(персонаж, гипотеза)
             
      CLAUSES 
      	возможный_вор(лЯгушенок).
      	возможный_вор(лакей).
      	возможный_вор(валет).
      	
      	возможная_роль(вор).
      	возможная_роль(не_вор).
      	
             возможная_истинность(правда).
             возможная_истинность(ложь).
      	
      	генерация_гипотезы([
      		персонаж(лЯгушенок, РольЛягушенка, ИстинностьЛягушенка),
      		персонаж(лакей, РольЛакея, ИстинностьЛакея),
      		персонаж(валет, РольВалета, ИстинностьВальта)
      	]):-
      		возможная_роль(РольЛягушенка), 
      		возможная_роль(РольЛакея), 
      		возможная_роль(РольВалета),
      		
      		возможная_истинность(ИстинностьЛягушенка),
      		возможная_истинность(ИстинностьЛакея),
      		возможная_истинность(ИстинностьВальта).
      		
      	сказал(лЯгушенок, Гипотеза):-
      		входит_в(персонаж(лакей, вор,_ИстинностьЛакея), Гипотеза).
      	сказал(лакей, Гипотеза):-
      		входит_в(персонаж(лакей, РольЛакея,_ИстинностьЛакея), Гипотеза),
      		NOT(РольЛакея = вор).
      	сказал(валет, Гипотеза):-
      		входит_в(персонаж(валет, вор,_ИстинностьВальта), Гипотеза).
      	проверка_высказывания(Кто, Гипотеза):-
      		входит_в(персонаж(Кто, _Роль, правда), Гипотеза),
      		сказал(Кто, Гипотеза);
      		
      		входит_в(персонаж(Кто, _Роль, ложь), Гипотеза),
      		NOT(сказал(Кто, Гипотеза)).
      	
      	входит_в(Элемент, [Элемент|_ОстальныеЭлементы]).
      	входит_в(Элемент, [_ПервыйЭлемент|ОстальныеЭлементы]):-
      		входит_в(Элемент, ОстальныеЭлементы).
      		
      	сколько_солгали([], 0).
      	сколько_солгали([Первый|Остальные], Количество):-
      		Первый = персонаж(_Имя, _Роль, ложь),
      		сколько_солгали(Остальные, КоличествоОстальныхЛжецов),
      		Количество = КоличествоОстальныхЛжецов + 1.
      	сколько_солгали([Первый|Остальные], Количество):-
      		Первый = персонаж(_Имя, _Роль, правда),
      		сколько_солгали(Остальные, Количество).
      		
      	проверка_гипотезы(Гипотеза):-
      		% не более чем один лгал
      		сколько_солгали(Гипотеза, 1),
      		
      		проверка_высказывания(лЯгушенок, Гипотеза),
      		проверка_высказывания(лакей, Гипотеза),
      		проверка_высказывания(валет, Гипотеза).
      		
      		
      GOAL    
              генерация_гипотезы(Гипотеза),
              проверка_гипотезы(Гипотеза).
      

      Решение 5

      DOMAINS 
      	имя = лягушенок; лакей; валет
      	роль = вор;не_вор
      	персонаж = персонаж(имя, роль, истинность)
      	истинность = правда;ложь
      	
      	гипотеза = персонаж*
      	имена = имя*
      	
      	решение = воры(имена)
      PREDICATES      
             nondeterm возможный_вор(имя)
             nondeterm возможная_роль(роль)
             nondeterm возможная_истинность(истинность)
                
             nondeterm генерация_гипотезы(гипотеза)
             nondeterm проверка_гипотезы(гипотеза)
             
             nondeterm сказал(имя, гипотеза)
             
             nondeterm проверка_высказывания(имя, гипотеза)
             
             nondeterm сколько_солгали(гипотеза, integer)
             
             nondeterm входит_в(персонаж, гипотеза)
             
             nondeterm солгал_не_более_чем_один(гипотеза)
             
             nondeterm гипотеза_в_решение(гипотеза, решение)
             
             nondeterm поиск_решения(решение)
             
      CLAUSES 
      	возможный_вор(лягушенок).
      	возможный_вор(лакей).
      	возможный_вор(валет).
      	
      	возможная_роль(вор).
      	возможная_роль(не_вор).
      	
             возможная_истинность(правда).
             возможная_истинность(ложь).
      	
      	генерация_гипотезы([
      		персонаж(лЯгушенок, РольЛягушенка, ИстинностьЛягушенка),
      		персонаж(лакей, РольЛакея, ИстинностьЛакея),
      		персонаж(валет, РольВалета, ИстинностьВальта)
      	]):-
      		возможная_роль(РольЛягушенка), 
      		возможная_роль(РольЛакея), 
      		возможная_роль(РольВалета),
      		
      		возможная_истинность(ИстинностьЛягушенка),
      		возможная_истинность(ИстинностьЛакея),
      		возможная_истинность(ИстинностьВальта).
      		
      	сказал(лЯгушенок, Гипотеза):-
      		входит_в(персонаж(лакей, вор,_ИстинностьЛакея), Гипотеза).
      	сказал(лакей, Гипотеза):-
      		входит_в(персонаж(лакей, РольЛакея,_ИстинностьЛакея), Гипотеза),
      		NOT(РольЛакея = вор).
      	сказал(валет, Гипотеза):-
      		входит_в(персонаж(валет, вор,_ИстинностьВальта), Гипотеза).
      	проверка_высказывания(Кто, Гипотеза):-
      		входит_в(персонаж(Кто, _Роль, правда), Гипотеза),
      		сказал(Кто, Гипотеза);
      		
      		входит_в(персонаж(Кто, _Роль, ложь), Гипотеза),
      		NOT(сказал(Кто, Гипотеза)).
      	
      	входит_в(Элемент, [Элемент|_ОстальныеЭлементы]).
      	входит_в(Элемент, [_ПервыйЭлемент|ОстальныеЭлементы]):-
      		входит_в(Элемент, ОстальныеЭлементы).
      		
      	сколько_солгали([], 0).
      	сколько_солгали([Первый|Остальные], Количество):-
      		Первый = персонаж(_Имя, _Роль, ложь),
      		сколько_солгали(Остальные, КоличествоОстальныхЛжецов),
      		Количество = КоличествоОстальныхЛжецов + 1.
      	сколько_солгали([Первый|Остальные], Количество):-
      		Первый = персонаж(_Имя, _Роль, правда),
      		сколько_солгали(Остальные, Количество).
      		
      	солгал_не_более_чем_один(Гипотеза):-
      		сколько_солгали(Гипотеза, 1);
      		сколько_солгали(Гипотеза, 0).
      		
      	проверка_гипотезы(Гипотеза):-
      		% не более чем один лгал
      		солгал_не_более_чем_один(Гипотеза),
      		
      		проверка_высказывания(лягушенок, Гипотеза),
      		проверка_высказывания(лакей, Гипотеза),
      		проверка_высказывания(валет, Гипотеза).
      		
      	гипотеза_в_решение(Гипотеза, Решение):-
      		findall(Имя, входит_в(персонаж(Имя, вор, _Истинность), Гипотеза), Воры),
      		Решение = воры(Воры).
      		
      	поиск_решения(Решение):-
      		 генерация_гипотезы(Гипотеза),
              	проверка_гипотезы(Гипотеза),
              	гипотеза_в_решение(Гипотеза, Решение).
      		
      		
      GOAL    
      	поиск_решения(Решение).
              /*генерация_гипотезы(Гипотеза),
              проверка_гипотезы(Гипотеза),
              гипотеза_в_решение(Гипотеза, Решение).*/
      

      Решение 6

      domains 
      	имя = лягушонок; лакей; валет
      	да_нет = да;нет
      	честность = вор_ли(да_нет)
      	структура_гипотезы = подозреваемый(имя, честность)
      	
      	гипотеза = структура_гипотезы*
      	имена = имя*
      	логические = да_нет*
      constants
      	все_имена = [лягушонок, лакей, валет]
      predicates      
             nondeterm входит_в(структура_гипотезы, гипотеза)
             nondeterm входит_в(да_нет, логические)
             nondeterm входит_в(имя, имена)
             nondeterm возможная_честность(да_нет)
             
             nondeterm генерация_гипотезы(гипотеза)
             
             nondeterm сказал(имя, гипотеза)
             nondeterm солгал(имя, гипотеза)
             nondeterm проверка_гипотезы(гипотеза)
             
             nondeterm решение(имя)
      CLAUSES 
      	возможная_честность(да).
      	возможная_честность(нет).
      	
      	входит_в(Элемент, [Элемент|_ОстальныеЭлементы]).
      	входит_в(Элемент, [_ПервыйЭлемент|ОстальныеЭлементы]):-
      		входит_в(Элемент, ОстальныеЭлементы).
      	
      	генерация_гипотезы(Гипотеза):-
      		возможная_честность(А), 
      		возможная_честность(Б), 
      		возможная_честность(В),
      		
      		% кто-то украл
      		входит_в(да, [А, Б, В]),
      		
      		Гипотеза = [
      			подозреваемый(лягушонок, вор_ли(А)),
      			подозреваемый(лакей, вор_ли(Б)),
      			подозреваемый(валет, вор_ли(В))
      		].
      		
      % Лягушонок. Сковороду украл Лакей-Лещ.
      	сказал(лягушонок, Гипотеза):-
      		входит_в(подозреваемый(лакей, вор_ли(да)), Гипотеза).
      		
      % Лакей-Лещ. Ваше Величество, не крал я никакой сковороды.
      	сказал(лакей, Гипотеза):-
      		входит_в(подозреваемый(лакей, вор_ли(нет)), Гипотеза).
      		
      % Валет Червей. Я украл сковороду!		
      	сказал(валет, Гипотеза):-
      		входит_в(подозреваемый(валет, вор_ли(да)), Гипотеза).
      		
      	солгал(Имя, Гипотеза):-
      		входит_в(Имя, все_имена),
      		сказал(Имя, Гипотеза).
      		
      	проверка_гипотезы(Гипотеза):-
      		% Выяснилось, что не более чем один подсудимый лгал.
      		findall(Имя, солгал(Имя, Гипотеза), Солгали),
      		Солгали = [_ЕдинственныйВрун],
      		
      		% Кто украл сковороду? 
      		% в единственном числе, т.е. вор один
      		findall(Имя, входит_в(подозреваемый(Имя, вор_ли(да)), Гипотеза), Воры),
      		Воры = [_ЕдинственныйВор].
      	
      	решение(Имя):-
      		генерация_гипотезы(Гипотеза),
              	проверка_гипотезы(Гипотеза),
              	
              	входит_в(подозреваемый(Имя, вор_ли(да)), Гипотеза).
      GOAL    
              решение(Вор).
      

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.