Логология Пролога / Головоломка Эйнштейна
Проблема в
Браун, Кларк, Джонс и Смит являются четырьмя существенными гражданами, которые служат сообществу как архитектор, банкир, врач и юрист, хотя и не обязательно соответственно. Браун, который более консервативен, чем Джонс, но более либерален, чем Смит, является лучшим игроком в гольф, чем мужчины, которые старше его и имеют больший доход, чем мужчины, которые моложе Кларка
Банкир, который зарабатывает больше, чем архитектор, не является ни самым молодым, ни самым старым.
Доктор, который является более бедным игроком в гольф, чем юрист, менее консервативен, чем архитектор
Как и следовало ожидать, самый старый мужчина самый консервативный и имеет наибольший доход, а самый молодой - лучший игрок в гольф
какая профессия у каждого человека?
Я написала
jobs(L) :- L = [[brown,_,_,_,_,_],
[clark,_,_,_,_,_],
[jones,_,_,_,_,_],
[smith,_,_,_,_,_]],
% [name,job,conservative,golf,income,age]
% conserative: 1 = least conservative, 4 = most conservative
% golf: 1 = worst golfer, 4 = best golfer
% income: 1 = least income, 4 = highest income
% age: 1 = youngest, 4 = oldest
% Brown is more conservative than Jones. Brown is less conservative than Smith.
member([brown,_,C1,_,_,_],L),
member([jones,_,C2,_,_,_],L),
C1 > C2,
member([smith,_,C3,_,_,_],L),
C1 < C3,
% Brown is a better golfer than those older than him.
member([brown,_,_,G1,_,A1],L),
member([_,_,_,G2,_,A2],L),
G1 > G2,
A2 > A1,
% Brown has a higher income than those younger than Clark.
member([brown,_,_,_,I1,_],L),
member([clark,_,_,_,_,A3],L),
member([_,_,_,_,I2,A4],L),
I1 > I2,
A3 > A4,
% Banker has a higher income than architect. Banker is neither youngest nor oldest.
member([_,banker_,_,I3,A5],L),
member([_,architect,_,_,I4,_],L),
I3 > I4,
(A5 = 2;A5 = 3),
% Doctor is a worse golfer than lawyer. Doctor is less conservative than architect.
member([_,doctor,C4,G3,_,_],L),
member([_,lawyer,_,G4,_,_],L),
member([_,architect,C5,_,_,_],L),
G3 < G4,
C4 < C5,
% Oldest is most conservative and has highest income.
member([_,_,4,_,4,4],L),
% Youngest is the best golfer.
member([_,_,_,4,_,1],L).
Когда я спрашиваю это
?- jobs(L).
я получил
ERROR: >/2: Arguments are not sufficiently instantiated
Я не уверен, что означает ошибка, я думаю, что я перевел все подсказки.
5 ответов
Ваш код работает точно так же, как и ожидалось, если вы просто используете конечные доменные ограничения вместо низкоуровневой арифметики. Например, используйте (#>)/2 вместо (>)/2,
После того, как вы заставите его работать за пределами этой ошибки создания экземпляра с помощью ограничений, вы заметите, что среди прочего ваш код имеет опечатку: banker_, Кроме того, вы не формулируете смысл правильно, и поэтому ваш предикат даст false,
Вот немного измененная версия вашего кода, измененная для использования ограничений конечного домена и исправления двух упомянутых ошибок:
:- use_module(library(clpfd)).
older_worse_golfer([], _, _).
older_worse_golfer([[_,_,_,G,_,A]|Rest], G0, A0) :-
A #> A0 #==> G #< G0,
older_worse_golfer(Rest, G0, A0).
younger_higher_income([], _, _).
younger_higher_income([[_,_,_,_,I,A]|Rest], I0, A0) :-
A #< A0 #==> I0 #> I,
younger_higher_income(Rest, I0, A0).
man_profession_rest([M,P|Rest], M-P, Rest).
jobs(Ls, Vs) :-
Ls = [[brown,_,_,_,_,_],
[clark,_,_,_,_,_],
[jones,_,_,_,_,_],
[smith,_,_,_,_,_]],
maplist(man_profession_rest, Ls, _, Rests),
append(Rests, Vs),
Vs ins 1..4,
% [name,job,conservative,golf,income,age]
% conserative: 1 = least conservative, 4 = most conservative
% golf: 1 = worst golfer, 4 = best golfer
% income: 1 = least income, 4 = highest income
% age: 1 = youngest, 4 = oldest
% Oldest is most conservative and has highest income.
member([_,_,4,_,4,4], Ls),
% Brown is more conservative than Jones. Brown is less
% conservative than Smith.
memberchk([brown,_,C1,_,_,_], Ls),
memberchk([jones,_,C2,_,_,_], Ls),
memberchk([smith,_,C3,_,_,_], Ls),
C1 #> C2,
C1 #< C3,
% Brown is a better golfer than those older than him.
memberchk([brown,_,_,G1,_,A1], Ls),
older_worse_golfer(Ls, G1, A1),
% IMPLIED: Brown is not the oldest
A1 #< 4,
% Brown has a higher income than those younger than Clark.
memberchk([brown,_,_,_,I1,_], Ls),
memberchk([clark,_,_,_,_,A3], Ls),
younger_higher_income(Ls, I1, A3),
% IMPLIED: Clark is not the youngest
A3 #> 1,
% Banker has a higher income than architect. Banker is neither
% youngest nor oldest.
I3 #> I4,
A5 in 2..3,
member([_,banker,_,_,I3,A5], Ls),
member([_,architect,_,_,I4,_], Ls),
% Doctor is a worse golfer than lawyer. Doctor is less
% conservative than architect.
member([_,doctor,C4,G3,_,_], Ls),
member([_,lawyer,_,G4,_,_], Ls),
member([_,architect,C5,_,_,_], Ls),
G3 #< G4,
C4 #< C5,
% Youngest is the best golfer.
member([_,_,_,4,_,1], Ls).
Ты можешь использовать label/1 искать конкретные решения. Как видно из следующего запроса, существует уникальное решение в отношении профессий:
?- time(setof(MP, Ls^Vs^Rs^(jobs(Ls, Vs),
label(Vs),
maplist(man_profession_rest, Ls, MP, Rs)), MP)).
который дает:
% 124,485 inferences, 0.041 CPU in 0.042 seconds (97% CPU, 3043643 Lips)
MP = [[brown-banker, clark-doctor, jones-architect, smith-lawyer]].
И это даже не требует, чтобы все уровни дохода и т. Д. Были разными. Если вы хотите, вы можете легко выразить это ограничение, добавив:
transpose(Rests, RestsT), maplist(all_different, RestsT)
к этой формулировке.
(продолжая путь, проложенный CapelliC...) Выбор из доменов и (еще лучше, пока) применение правил - это обычно путь в таких головоломках. Тщательно проверяйте как можно скорее, чтобы как можно скорее устранить неправильный выбор, но не раньше.
Мы не можем арифметически сравнивать неизвестные значения, вот что означает ошибка: > сравнивает два известных арифметических значения, для которых создаются его аргументы. Но если логическая переменная Prolog еще не создана, это означает, что ее значение все еще неизвестно.
В логическом программировании ограничений (CLP) мы можем зарегистрировать такие ограничения заранее, но не в ванильном Прологе. Хотя многие современные Prolog имеют пакеты CLP или предикаты, доступные в них. У SWI Prolog это тоже есть. Но в ванильном коде Пролога мы должны быть осторожны.
mselect([A|As],S,Z):- select(A,S,S1), mselect(As,S1,Z).
mselect([],Z,Z). %// instantiate a domain by selecting from it
puzzle(L):- %// [_,_,Conserv,Golf,Income,Age]
L = [ [brown,_,C1,G1,I1,A1],
[clark,_,C2,_ ,I2,A2],
[jones,_,C3,_ ,I3,A3],
[smith,_,C4,_ ,I4,A4] ],
L1 = [[_,_,4,_,4,4], [_,_,_,4,_,1]], %// 6,7 - oldest, youngest
mselect( L1, L, L2), %// L2: neither youngest nor oldest
mselect( [A3,A4], [1,2,3,4], [A2,A1]), A2 > 1, %// 3b. 1 < A2 < A1
select( C2, [1,2,3,4], [C3,C1,C4]), %// 1. C3 < C1 < C4
select( [_, banker, _ ,GB,IB,_ ], L2, [P3] ),
mselect( [ [_, archct, CA,GA,IA,_ ], %// second view into the same matrix
[_, doctor, CD,GD,ID,_ ] ], [P3|L1],
[ [_, lawyer, _ ,GL,IL,_ ] ] ),
CD < CA, %// 5b.
mselect( [ID,IL], [1,2,3,4], [IA,IB]), %// 4a. IA < IB
mselect( [GA,GB], [1,2,3,4], [GD,GL]), %// 5a. GD < GL
%// 2. ( X in L : A1 < AX ) => G1 > GX
%// 3. ( Y in L : AY < A2 ) => I1 > IY ... so, not(A1<A2)! i.e. % 3b. 1 < A2 < A1
forall( (member(X,L), last(X,AX), AX>A1), (nth1(4,X,GX), G1>GX) ),
forall( (member(Y,L), last(Y,AY), A2>AY), (nth1(5,Y,IY), I1>IY) ).
Тестирование: ([_,_,Conserv,Golf,Income,Age])
7 ?- time(( puzzle(_X), maplist(writeln,_X),nl, false; true )).
[brown,banker,3,3,3,3]
[clark,doctor,1,1,1,2]
[jones,archct,2,4,2,1]
[smith,lawyer,4,2,4,4]
[brown,banker,3,3,3,3]
[clark,doctor,1,1,2,2]
[jones,archct,2,4,1,1]
[smith,lawyer,4,2,4,4]
[brown,banker,3,3,2,3]
[clark,doctor,1,1,3,2]
[jones,archct,2,4,1,1]
[smith,lawyer,4,2,4,4]
%// 2,299 inferences, 0.000 CPU in 0.120 seconds (0% CPU, Infinite Lips)
true.
На самом деле это одно из решений, в зависимости от того, как задан вопрос головоломки.
Вот мой ответ на проблему:
puzzle(Puzzle) :-
Names = [brown,clark,jones,smith],
permute(Names,Conservatives),
% Brown is more conservative than Jones.
ismore(brown,jones,Conservatives),
% Brown is less conservative than Smith.
isless(brown,smith,Conservatives),
permute(Names,Golfs),
permute(Names,Ages),
% Brown is a better golfer than those older than him.
worsethans(brown,Golfs,WorseAtGolfThanBrown),
betterthans(brown,Ages,OlderThanBrown),
members(OlderThanBrown,WorseAtGolfThanBrown),
permute(Names,Incomes),
% Brown has a higher income than those younger than Clark.
worsethans(brown,Incomes,WorseIncomeThanBrown),
worsethans(clark,Ages,YoungerThanClark),
members(YoungerThanClark,WorseIncomeThanBrown),
permute([banker,architect,lawyer,doctor],Jobs),
% Banker has a higher income than architect.
lookup(banker,Jobs,Names,Banker),
lookup(architect,Jobs,Names,Architect),
ismore(Banker,Architect,Incomes),
% Banker is neither youngest nor oldest.
([_,Banker,_,_]=Ages;[_,_,Banker,_]=Ages),
% Doctor is a worse golfer than lawyer.
lookup(doctor,Jobs,Names,Doctor),
lookup(lawyer,Jobs,Names,Lawyer),
ismore(Lawyer,Doctor,Golfs),
% Doctor is less conservative than architect.
ismore(Architect,Doctor,Conservatives),
% Oldest is most conservative and has highest income.
[Oldest,_,_,_]=Ages,
[Oldest,_,_,_]=Conservatives,
[Oldest,_,_,_]=Incomes,
% Youngest is the best golfer.
[_,_,_,Youngest]=Ages,
[Youngest,_,_,_]=Golfs,
Puzzle = [Names,Jobs,c(Conservatives),g(Golfs),i(Incomes),a(Ages)].
Нужны эти поддерживающие предикаты:
ismore(X,Y,Zs) :-
append(Xs,[Y|_],Zs),
member(X,Xs).
isless(X,Y,Zs) :-
append(_,[Y|Xs],Zs),
member(X,Xs).
betterthans(X,Ys,Zs) :-
append(Zs,[X|_],Ys).
worsethans(X,Ys,Zs) :-
append(_,[X|Zs],Ys).
%lookup(X,Xs,Ys,Y)
lookup(X,[X|_],[Y|_],Y).
lookup(X,[_|Xs],[_|Ys],Y) :-
lookup(X,Xs,Ys,Y).
members([], _).
members([X|Xs], Ys) :-
member(X, Ys),
members(Xs, Ys).
select([X|Xs], X, Xs).
select([X|Xs], Y, [X|Ys]) :- select(Xs, Y, Ys).
permute([], []).
permute(Xs, [X|Zs]) :-
select(Xs, X, Ys),
permute(Ys, Zs).
Теперь единственная проблема, с которой я столкнулся, это то, что это дает мне более одного ответа. Если у меня нет логики неправильно, это то, что я понял:
[[brown,clark,jones,smith],[banker,architect,doctor,lawyer],c([smith,brown,clark,jones]),g([clark,brown,smith,jones]),i([smith,brown,clark,jones]),a([smith,brown,jones,clark])]
[[brown,clark,jones,smith],[banker,architect,doctor,lawyer],c([smith,brown,clark,jones]),g([clark,brown,smith,jones]),i([smith,brown,jones,clark]),a([smith,brown,jones,clark])]
[[brown,clark,jones,smith],[banker,architect,doctor,lawyer],c([smith,brown,clark,jones]),g([clark,brown,smith,jones]),i([smith,jones,brown,clark]),a([smith,brown,jones,clark])]
[[brown,clark,jones,smith],[banker,architect,doctor,lawyer],c([smith,brown,clark,jones]),g([clark,brown,smith,jones]),i([smith,brown,clark,jones]),a([smith,jones,brown,clark])]
[[brown,clark,jones,smith],[banker,architect,doctor,lawyer],c([smith,brown,clark,jones]),g([clark,brown,smith,jones]),i([smith,brown,jones,clark]),a([smith,jones,brown,clark])]
[[brown,clark,jones,smith],[banker,architect,doctor,lawyer],c([smith,brown,clark,jones]),g([clark,brown,smith,jones]),i([smith,jones,brown,clark]),a([smith,jones,brown,clark])]
[[brown,clark,jones,smith],[banker,doctor,architect,lawyer],c([smith,brown,jones,clark]),g([jones,brown,smith,clark]),i([smith,brown,clark,jones]),a([smith,brown,clark,jones])]
[[brown,clark,jones,smith],[banker,doctor,architect,lawyer],c([smith,brown,jones,clark]),g([jones,brown,smith,clark]),i([smith,brown,jones,clark]),a([smith,brown,clark,jones])]
[[brown,clark,jones,smith],[banker,doctor,architect,lawyer],c([smith,brown,jones,clark]),g([jones,brown,smith,clark]),i([smith,clark,brown,jones]),a([smith,brown,clark,jones])]
[[brown,clark,jones,smith],[banker,architect,doctor,lawyer],c([smith,clark,brown,jones]),g([clark,brown,smith,jones]),i([smith,brown,clark,jones]),a([smith,brown,jones,clark])]
[[brown,clark,jones,smith],[banker,architect,doctor,lawyer],c([smith,clark,brown,jones]),g([clark,brown,smith,jones]),i([smith,brown,jones,clark]),a([smith,brown,jones,clark])]
[[brown,clark,jones,smith],[banker,architect,doctor,lawyer],c([smith,clark,brown,jones]),g([clark,brown,smith,jones]),i([smith,jones,brown,clark]),a([smith,brown,jones,clark])]
[[brown,clark,jones,smith],[banker,architect,doctor,lawyer],c([smith,clark,brown,jones]),g([clark,brown,smith,jones]),i([smith,brown,clark,jones]),a([smith,jones,brown,clark])]
[[brown,clark,jones,smith],[banker,architect,doctor,lawyer],c([smith,clark,brown,jones]),g([clark,brown,smith,jones]),i([smith,brown,jones,clark]),a([smith,jones,brown,clark])]
[[brown,clark,jones,smith],[banker,architect,doctor,lawyer],c([smith,clark,brown,jones]),g([clark,brown,smith,jones]),i([smith,jones,brown,clark]),a([smith,jones,brown,clark])]
Я могу ограничить это одним решением, если я также скажу, что доход Кларка больше, чем у Брауна.
Может ли кто-нибудь подтвердить, правильный ли мой ответ или нет, и должно ли быть больше ограничений?
Вам необходимо привязать ваши переменные к домену, прежде чем использовать их, самый простой способ - перестановка /2:
L = [ [brown,J1,C1,G1,I1,A1],
[clark,J2,C2,G2,I2,A2],
[jones,J3,C3,G3,I3,A3],
[smith,J4,C4,G4,I4,A4]],
permutation([1,2,3,4], [C1,C2,C3,C4]),
permutation([1,2,3,4], [I1,I2,I3,I4]),
permutation([1,2,3,4], [A1,A2,A3,A4]),
permutation([1,2,3,4], [G1,G2,G3,G4]),
permutation([banker,archit,doctor,lawyer], [J1,J2,J3,J4]),
теперь можно использовать правила
% Brown is more conservative than Jones. Brown is less conservative than Smith.
member([brown,_,CB,GB,IB,AB],L),
member([jones,_,CJ,_,_,_],L),
CB > CJ,
member([smith,_,CS,_,_,_],L),
CB < CS,
с точки зрения эффективности, когда вы выбираете (через член) именованный член, "извлекайте" все связанные переменные одновременно (коричневые атрибуты используются позже). Также помните, что ссылки в различных переменных выбора J1,C1 и т. Д. Могут привести к нежелательному связыванию.
Правило, которое трудно выразить
% Brown is a better golfer than those older than him.
member([_,_,_,GO1,_,AO1],L),
(AO1 > AB, GB > GO1 ; AO1 < AB),
member([_,_,_,GO2,_,AO2],L),
(AO2 > AB, GB > GO2 ; AO2 < AB),
member([_,_,_,GO3,_,AO3],L),
(AO3 > AB, GB > GO3 ; AO3 < AB),
vardiff(GO1,GO2,GO3),
vardiff(AO1,AO2,AO3), % bug: AO1 was GO1
где vardiff/3 - простое удобство:
vardiff(A,B,C) :- A\=B,A\=C,B\=C.
Конечно, если у вас есть пролог, CLP(FD) - гораздо лучший выбор.
Мое решение основано на том, что сказал CapelliC
% [name,job,conservative,golf,income,age]
% conserative: 1 = least conservative, 4 = most conservative
% golf: 1 = worst golfer, 4 = best golfer
% income: 1 = lowest income, 4 = highest income
% age: 1 = youngest, 4 = oldest
jobs(L) :- L =
[[brown,J1,C1,G1,I1,A1],
[clark,J2,C2,G2,I2,A2],
[jones,J3,C3,G3,I3,A3],
[smith,J4,C4,G4,I4,A4]],
permutation([1,2,3,4], [C1,C2,C3,C4]),
permutation([1,2,3,4], [I1,I2,I3,I4]),
permutation([1,2,3,4], [A1,A2,A3,A4]),
permutation([1,2,3,4], [G1,G2,G3,G4]),
permutation([banker,architect,doctor,lawyer], [J1,J2,J3,J4]),
% Brown is more conservative than Jones. Brown is less conservative than Smith.
member([brown,_,CB,GB,IB,AB],L),
member([jones,_,CJ,_,_,_],L),
member([smith,_,CS,_,_,_],L),
CB > CJ,
CB < CS,
% Brown is a better golfer than those older than him.
member([_,_,_,G01,_,A01],L),
(A01 > AB, GB > G01 ; A01 < AB),
member([_,_,_,G02,_,A02],L),
(A02 > AB, GB > G02 ; A02 < AB),
member([_,_,_,G03,_,A03],L),
(A03 > AB, GB > G03 ; A03 < AB),
vardiff(G01,G02,G03),
vardiff(G01,A02,A03),
% Brown has a higher income than those younger than Clark.
member([clark,_,_,_,_,AC],L),
member([_,_,_,_,I01,A04],L),
(A04 < AC, IB > I01; AC < A04),
% Banker has a higher income than architect. Banker is neither youngest nor oldest.
member([_,banker,_,_,IBa,ABa],L),
member([_,architect,CAr,_,IAr,_],L),
IBa > IAr,
(ABa \= 1, ABa \= 4),
% Doctor is a worse golfer than lawyer. Doctor is less conservative than architect.
member([_,doctor,CDo,GDo,_,_],L),
member([_,lawyer,_,GLa,_,_],L),
GDo < GLa,
CDo < CAr,
% Oldest is most conservative and has highest income.
member([_,_,4,_,4,4],L),
% Youngest is the best golfer.
member([_,_,_,4,_,1],L).
vardiff(A,B,C) :- A\=B, A\=C, B\=C.
я получил
3 ?- jobs(L).
L = [[brown,architect,2,4,1,1],[clark,banker,3,1,2,2],[jones,doctor,1,2,3,3],[smith,lawyer,4,3,4,4]] ;
L = [[brown,architect,2,4,1,1],[clark,banker,3,2,2,2],[jones,doctor,1,1,3,3],[smith,lawyer,4,3,4,4]] ;
L = [[brown,architect,2,4,1,1],[clark,banker,3,3,2,2],[jones,doctor,1,1,3,3],[smith,lawyer,4,2,4,4]] ;
L = [[brown,architect,2,4,1,1],[clark,banker,3,1,2,3],[jones,doctor,1,2,3,2],[smith,lawyer,4,3,4,4]] ;
L = [[brown,architect,2,4,1,1],[clark,banker,3,2,2,3],[jones,doctor,1,1,3,2],[smith,lawyer,4,3,4,4]] ;
L = [[brown,architect,2,4,1,1],[clark,banker,3,3,2,3],[jones,doctor,1,1,3,2],[smith,lawyer,4,2,4,4]] ;
L = [[brown,architect,2,4,1,1],[clark,banker,3,1,3,2],[jones,doctor,1,2,2,3],[smith,lawyer,4,3,4,4]] ;
L = [[brown,architect,2,4,1,1],[clark,banker,3,2,3,2],[jones,doctor,1,1,2,3],[smith,lawyer,4,3,4,4]] ;
L = [[brown,architect,2,4,1,1],[clark,banker,3,3,3,2],[jones,doctor,1,1,2,3],[smith,lawyer,4,2,4,4]] ;
L = [[brown,architect,2,4,1,1],[clark,banker,3,1,3,3],[jones,doctor,1,2,2,2],[smith,lawyer,4,3,4,4]] ;
L = [[brown,architect,2,4,1,1],[clark,banker,3,2,3,3],[jones,doctor,1,1,2,2],[smith,lawyer,4,3,4,4]] ;
L = [[brown,architect,2,4,1,1],[clark,banker,3,3,3,3],[jones,doctor,1,1,2,2],[smith,lawyer,4,2,4,4]] ;
Несколько повторяющихся ответов, поэтому я удалил некоторые из них.
Все подсказки удовлетворены, за исключением случаев, когда Кларк, например, второй по возрасту
L = [[brown,architect,2,4,1,1],[clark,banker,3,1,2,3],[jones,doctor,1,2,3,2],[smith,lawyer,4,3,4,4]] ;
Эта подсказка нарушена
% Brown has a higher income than those younger than Clark.
И для всех моих ответов Браун самый молодой, так что подсказки, как
% Brown is a better golfer than those older than him.
% Brown has a higher income than those younger than Clark.
% Youngest is the best golfer.
кажется немного бессмысленным...