Left(1,2). left(2,3). left(3,4). left(4,5)

Test(Colours,Drinks,Nationalities,Professions,Pets).

Рішення способом 1.

generate([L1, L2, L3, L4, L5]):-

perm(L1,[red,yellow,blue,green,white]),

perm(L2,[juice,tea,coffee,milk,water]),

perm(L3,[english,spanish,japanese,norwegian,italian]),

perm(L4,[diplomat,sculptor,painter,musician,doctor]),

perm(L5,[dog,fox,snails,horse,zebra]).

perm([U:A,V:B,X:C,Y:D,Z:E],L):-

permute([A,B,C,D,E], [1,2,3,4,5]), [U,V,X,Y,Z] = L.

permute([],[]).

permute(L,[X|T]):- remove(X,L,R),permute(R,T).

remove(X,[X|T],T).

remove(X,[H|T],[H|R]):- remove(X,T,R).

test(C, D, N, S, P):-

% Англієць живе в червоному домі

member(english:H1, N), member(red:H1,C),

% У Іспанця є собака

member(spanish:H2, N), member(dog:H2,P),

% Японець є художником

member(japanese:H11, N),member(painter:H11, S),

% Італієць п’є чай

member(italian:H10, N),member(tea:H10, D),

% Норвежець живе в першому домі зліва

member(norwegian:1, N),

% Власник зеленого дома п’є кофе

member(coffee:H14, D),member(green:H14, C),

% Зелений дом розташований праворуч від білого

member(green:H15,C),left(H16, H15),member(white:H16,C),

% Скульптор вирощує равликів

member(sculptor:H8, S),member(snails:H8, P),

% Дипломат живе в жовтому домі

member(diplomat:H3, S),member(yellow:H3, C),

% В домі посередині пьют молоко

member(milk:3, D),

% Норвежець живе поряд з блакитним домом

member(norwegian:H6,N),next(H6, H7),member(blue:H7,C),

% Скрипаль п’є фруктові соки

member(musician:H9, S),member(orange_juice:H9, D),

% Лиса тримають в домі по-сусідству з домом лікаря

member(doctor:H4, S), next(H4, H5),member(fox:H5, P),

% Коня тримають в домі по-сусідству з домом дипломата

member(diplom:H12,S),next(H12, H13),member(horse:H13,P),

% Хтось тримає зебру и хтось п’є воду

member(zebra:_, P), member(water:_, D).

next(X,Y):- left(X,Y); left(Y,X).

Метод породження й перевірок вимагає розгляду (5!)⁵ варіантів розв'язку (25 мільярдів). При породженні породжується значне число рішень, які потім відкидаються предикатами member.

Рішення способом 2.

Скористаємось тим фактом, що предикати member здатні самі генерувати рішення. Generate буде повертати частково-конкретезований шаблон списку.

generate([]).

generate([L|T]):- perm(L), generate(T).

perm([_:A,_:B,_:C,_:D,_:E]):-

permute([A,B,C,D,E], [1,2,3,4,5]).

permute([],[]).

permute(L,[X|T]):- remove(X,L,R),permute(R,T).

remove(X,[X|T],T).

remove(X,[H|T],[H|R]):- remove(X,T,R).

Метод гілок і границь.

Метод гілок і границь дозволяє відітнути й не розглядати цілі гілки дерева. Насправді, якщо предикат test має вигляд test(C):- test1(C), test2(C), …, то в неявному виді використовується метод гілок і границь. Перехід до шаблонного подання списку дозволяє більшою мірою використовувати ідею методу гілок і границь.

Рішення способом 3.

Стан задачі:

S = [h(національність1, професія1, колір1, тварина1, напій1), …] – в порядку переліку будинків

solve(S):- Street =

[h(norwegian,_,_,_,_),h(_,_,blue,_,_),h(_,_,_,_,milk),_,_],

Дата добавления: 2014-01-04