Ответ в теме: Алиса в стране чудес – Prolog. В некоторой далекой стране

      Комментарии к записи Ответ в теме: Алиса в стране чудес – Prolog. В некоторой далекой стране отключены
#2058

Рыцарь всегда говорит правду, а шпион – всегда врет, т.е. в любом случае они не могут дать сразу два утверждения.
Утверждения мы поместим в базу данных. Так, например, информация о том, что второй человек является шпионом может быть записана так: [_A, shpion, _C]. Первый и последний элемент списка не связан, т.е. он может иметь любое значение – возникает проблема сравнения таких записей. Поэтому в базе данных я бы хранил сразу наборы высказываний (это не единственное решение, но мне оно кажется самым простым).

Объявим типы данных – юнит (может являться рыцарем, лжецом или шпионом), одно высказывание (список юнитов), набор высказываний:

domains
	unit=ricar;shpion;lzhec
	units=unit*
	says = units*

В разделе predicates опишем прототипы используемых функций:

predicates
	nondeterm solve(units)
	nondeterm try(unit) 
	
	say(integer, says)
	
	nondeterm can_be_ricar_or_lzhec(integer)
	
	nondeterm length(says, integer)
	nondeterm pos(unit, units, integer)
	
	nondeterm process(integer, units)
	nondeterm processSays(units, says)

Функция solve используется для подбора решения (перебора всех видов персонажей):

try(ricar).
try(lzhec).
try(shpion).

Правило length является стандартным, однако оно немного изменено в связи с тем, что запрещено использовать оператор отсечения в Prolog:

length(List, Length):-
  List = [], Length = 0;
  List = [_Head|Tail], length(Tail, TailLength), Length = TailLength + 1.

Функция pos возвращает позицию элемента с заданным значением в списке. Если элемента нет, то правило завершится неудачей – мы используем это чтобы гарантировать, что решение содержит обязательно одного лжеца, одного шпиона и одного рыцаря.

pos(Element, [Element|_Tail], 0).
pos(Element, [Head|Tail], Index):-
  NOT(Element=Head),
  pos(Element, Tail, TailPos), 
  Index = TailPos + 1.

Если первый элемент списка содержит искомое значение – функция возвращает ноль, т.к. мы решили с нуля начинать индексацию элементов. Вернув ноль стоило бы поставить оператор отсечения, однако т.к. его использование запрещено – остальные ветви алгоритма должны выполнять дополнительную проверку чтобы убедиться, что первый элемент не является искомым. Рекурсивным вызовом обрабатываются элементы списка, за исключением первого, поэтому к полученному результату добавляется единица.

Предикат nondeterm can_be_ricar_or_lzhec проверяет возможность размещения рыцаря или лжеца на заданной позиции. Они оба могли дать только одно утверждение – поэтому достаточно получить список их высказываний и сравнить его длину с единицей:

can_be_ricar_or_lzhec(Index):-
  say(Index, Says), length(Says, 1).

В базе данных хранится информация о высказываниях юнита с заданным номером:

say(0, [[_A, shpion, _C]]).
say(1, [[_A, _B, shpion]]).
say(2, [[shpion, _B, _C], [_A, shpion, _C]]).

Функция solve выполняет поиск решения логической задачи, для этого запрашивает генерацию всех возможных сочетаний из трех юнитов. Юниты помещаются в список. Вызовом функций pos находятся позиции каждого типа юнита, а также гарантируется наличие каждого типа юнита в списке (иначе позицию определить невозможно). Проверяется возможность размещения рыцаря и лжеца на текущих позициях, а затем, для этих позиций вызывается функция process.

solve(Solution):-
  try(A), try(B), try(C), 
  Solution = [A, B, C],
  pos(lzhec, Solution, LzhecPos), pos(ricar, Solution, RicarPos), pos(shpion, Solution, _ShpionPos),
		
  can_be_ricar_or_lzhec(LzhecPos), can_be_ricar_or_lzhec(RicarPos),
		
  process(RicarPos, Solution), NOT(process(LzhecPos, Solution)).

Функция process принимает текущее решение и проверяет его на соответствие высказываниям юнита с заданным номером. В связи с этим для лжеца результат ее работы должен быть инвертирован оператором NOT. Функция извлекает из базы все высказывания персонажа и пытается применить их всех к решению (используя вспомогательную функцию processSays):

process(Index, Solution):-
  say(Index, Says), processSays(Solution, Says).
		
processSays(_Solution, []).
processSays(Solution, [HeadSay|TailSays]):-
  Solution = HeadSay, processSays(Solution, TailSays).

Функция processSays перебирает все высказывания из списка и каждое из них применяет к решению – для этого достаточно попробовать выполнить присваивание, т.к. незначащая часть высказываний является анонимными переменными и может быть присвоена чему угодно.