Загадка Эйнштейна На Prolog
Формулировка задачи:
Всем доброго времени суток!
Вот недавно только узнал об одной очень извесной головоломки Эйнштейна - "Who has a fish?".
И мне стало интерестно как можно решить эту головоломку при помощи Пролога. Я недавно только начал учить Prolog, поэтому моя попытка самому написать исходник не удалась. Искал в гугле исходники, но все примеры что я находил не казались мне понятными. Возможно тут есть те кто решал эту задачку...Дайте исходник и опишите текст проги, если не затруднит
Решение задачи: «Загадка Эйнштейна На Prolog»
textual
Листинг программы
DOMAINS s=string sl=s* sll=sl* slll=sll* sllll=slll* CONSTANTS st=[["1","Norwegian","","","",""],["2","","Blue","","",""],["3","","","Milk","",""],["4","","","","",""],["5","","","","",""]] PREDICATES inFact(slll) go(sll) solve(sllll,sll) member(slll,sll) insList(sll,sll,sll) insert(sll,sll,sll) inHouse(sl,sl,sl) CLAUSES go(Out):- findall(F,inFact(F),Facts), solve(Facts,Out). solve([],st):-!. solve([Fact|H],Out):- solve(H,O), member(Fact,F), insList(F,O,Out). insList(X,P,Pn):- insert(X,P,Pn). insList(X,[G|Y],[G|Z]):- !, insList(X,Y,Z). insert([],X,X):-!. insert([X|Y],[G|H],[Gn|Hn]):- inHouse(X,G,Gn), insert(Y,H,Hn). inHouse([],X,X):-!. inHouse([""|H],[X|Y],[X|Z]):- !, inHouse(H,Y,Z). inHouse([X|H],[X|Y],[X|Z]):- !, inHouse(H,Y,Z). inHouse([X|H],[""|Y],[X|Z]):- !, inHouse(H,Y,Z). member([X|_],X). member([_|X],Y):- member(X,Y). /*************************************************************/ inFact([[["","Englishman","Red"]]]). inFact([[["","Swede","","","","Dog"]]]). inFact([[["","Danish","","Tea"]]]). inFact([[["","","Green","Coffee"]]]). inFact([[["","","","","PallMall","Chicken"]]]). inFact([[["","","Yellow","","Dunhill"]]]). inFact([[["","","","Beer","Winfield"]]]). inFact([[["","German","","","Rothmans"]]]). inFact([[["","","","","","Fish"]]]). inFact([[["","","Green"],["","","White"]]]). inFact([[["","","","","Marlboro"],["","","","","","Cat"]], [["","","","","","Cat"],["","","","","Marlboro"]]]). inFact([[["","","","","Dunhill"],["","","","","","Horse"]], [["","","","","","Horse"],["","","","","Dunhill"]]]). inFact([[["","","","","Marlboro"],["","","","Water"]], [["","","","Water"],["","","","","Marlboro"]]]).
Объяснение кода листинга программы
- DOMAINS: определяются типы данных для переменных. В данном случае, s=string, sl=s, sll=sl, slll=sll, sllll=slll.
- CONSTANTS: определяются константы, используемые в задаче. В данном случае, это список строк [[
1,Norwegian,,,,],[2,,`Blue`,,,],[3,,,Milk,,],[4,,,,,],[`5`,,,,,]]. - PREDICATES: определяются функции, которые будут использоваться в программе. В данном случае, это функции inFact/1, go/1, solve/2, member/2, insList/3 и insert/3.
- CLAUSES: определяются правила, которые преобразуют исходную информацию в результат. В данном случае, это правило для функции go/1, которое находит все факты и передает их в функцию solve/2.
- solve/2: рекурсивная функция, которая решает задачу. Если входной список пуст, то функция завершается. В противном случае, она рекурсивно вызывает себя для оставшейся части списка и добавляет первый элемент в результат.
- insList/3: функция, которая добавляет элемент в список. В данном случае, она вызывает функцию insert/3 для добавления элемента в список.
- insert/3: функция, которая добавляет элемент в список. Если список пуст, то элемент добавляется в начало списка. В противном случае, функция рекурсивно вызывает себя для оставшейся части списка и добавляет элемент после последнего элемента списка.
- inHouse/3: функция, которая проверяет, находится ли элемент в доме (списке). Если дом пуст, то элемент считается находящимся в доме. В противном случае, функция рекурсивно вызывает себя для оставшейся части дома и проверяет, является ли элемент последним элементом дома.
- member/2: функция, которая проверяет, является ли элемент членом списка. Если элемент является пустой строкой, то он не является членом списка. В противном случае, функция рекурсивно вызывает себя для оставшейся части списка.
- inFact/1: определяются факты, которые будут использоваться в задаче. В данном случае, это список фактов [[
,`Englishman`,`Red`],[,Swede,,,Dog],[,`Danish`,,Tea],[,,Green,Coffee],[,,,,PallMall,Chicken],[,,Yellow,,`Dunhill`],[,,,Beer,Winfield],[,`German`,,,`Rothmans`],[,,,,,Fish],[,,Green],[,,White],[,,,,Marlboro],[,,,,Cat],[,,,,Marlboro],[,,,,Dunhill],[,,,,Horse],[,,,,Marlboro],[,,`,Water`]].