My IA assignment is to solve the Einstein Problem.
I must solve it using a CSP model in Prolog. I am not given the model, but only the problem and some input data. My solution must be a general one, I mean, for some input data I must offer a solution. The dimension of the problem is N, for example N may be 5(we have 5 houses), but it can vary.
Many solutions I have found on the Internet put the constrains directly in code, but I need to generate them using the input data. The problem must be solved using the MAC(Maintain Arc-Consistency) algorithm.
I have read a lot about it (Einstein's riddle). To implement the problem I need a representation of the problem.
The problem is, I don't know exactly how to represent the problem in Prolog(I know basic Prolog, haven't used additional libraries, we are not allowed to use clpfd library - the prolog clp solver).
I know I should create constraints form the input(the 14 clues) + the constrains that say all the variables from the same group(e.g. Nationality) should be different, I could implement I predicate like:
my_all_different(like all_different/1 offered by clpfd).
For example:
Attributes = ['Color', 'Nationality', 'Drink', 'Smoke', 'Pet'].
Values = [['Blue', 'Green', 'Ivory', 'Red', 'Yellow'],
['Englishman', 'Japanese', 'Norwegian', 'Spaniard', 'Ukrainian'],
['Coffee', 'Milk', 'Orange juice', 'Tea', 'Water'],
['Chesterfield', 'Kools', 'Lucky Strike', 'Old Gold', 'Parliament'],
['Dog', 'Fox', 'Horse', 'Snails', 'Zebra']
]).
Statements = 'The Englishman lives in the red house',
'The Spaniard owns the dog',
'Coffee is drunk in the green house',
'The Ukrainian drinks tea',
'The green house is immediately to the right of the ivory house',
'The Old Gold smoker owns snails',
'Kools are smoked in the yellow house',
'Milk is drunk in the middle house',
'The Norwegian lives in the first house',
'The man who smokes Chesterfield lives in the house next to the man with the fox',
'Kools are smoked in the house next to the house where the horse is kept',
'The Lucky Strike smoker drinks orange juice',
'The Japanese smokes Parliament',
'The Norwegian lives next to the blue house'
]).
Question = 'Who owns a zebra'?
Now, I managed to parse this input and obtained a list of lists:
R = [[red,englishman]
[spaniard,dog]
[green,coffee]
[ukrainian,tea]
[green,ivory,right]
[old,snails]
[yellow,kools]
[milk,middle]
[norwegian,first]
[chesterfield,fox,next]
[kools,horse,next]
[orange,lucky]
[japanese,parliament]
[blue,norwegian,next]].
Now I suppose I need to use this generated info to construct some constrains, from what I have read it would be a good idea to use binary constrains(represented as predicates I think), but I have some unary constraints too, so how should I represent constrains to include all of them?
Another problem is: how to represent the variables (where I'll have the computed data) so that I won't need to search and modify the lists(because in prolog you can't modify lists like in imperative languages).
So I thought using a list of variables, where each variable/element is represented by a 3-tuple: (var, domain, attrV), where var contains the current value of a variable, domain is a list say: [1, 2, 3, 4, .., N], and attrV is one value(of N) of the corresponding attribute(e.g. red). One element would be: (C, [1, 2, 3, 4, 5], red).
Other problems: How should I implement an MAC algorithm in prolog(uses AC-3 alorithm), because I'll have a queue of tuples and this queue will be modified if the constrains aren't met, and this means modifying the variables list, and again how should I modify the lists in Prolog.
Any help would be appreciated!
I tried to solve a particular version of the problem using the CSP solver from the link you gave above, but still I can't get to a solution,I want to obtain the solution, because in this manner, I 'll know how to represent correctly the constraints for the general version.
Added code:
% Computational Intelligence: a logical approach.
% Prolog Code.
% A CSP solver using arc consistency (Figure 4.8)
% Copyright (c) 1998, Poole, Mackworth, Goebel and Oxford University Press.
% csp(Domains, Relations) means that each variable has
% an instantiation to one of the values in its Domain
% such that all the Relations are satisfied.
% Domains represented as list of
% [dom(V,[c1,...,cn]),...]
% Relations represented as [rel([X,Y],r(X,Y)),...]
% for some r
csp(Doms,Relns) :-
write('CSP Level'), nl,
ac(Doms,Relns).
% ac(Dom,Relns) is true if the domain constrants
% specified in Dom and the binary relations
% constraints specified in Relns are satisfied.
ac(Doms,Relns) :-
make_arcs(Relns,A),
consistent(Doms,[],A,A),
write('Final Doms '), write(Doms), nl, %test
write('Final Arcs '), write(A), nl. %test
% make_arcs(Relns, Arcs) makes arcs Arcs corresponding to
% relations Relns. There are acrs for each ordering of
% variables in a relations.
make_arcs([],[]).
make_arcs([rel([X,Y],R)|O],
[rel([X,Y],R),rel([Y,X],R)|OA]) :-
make_arcs(O,OA).
% consistent(Doms,CA,TDA,A) is true if
% Doms is a set of domains
% CA is a set of consistent arcs,
% TDA is a list of arcs to do
% A is a list of all arcs
consistent(Doms,CA,TDA,A) :-
consider(Doms,RedDoms,CA,TDA),
write('Consistent Doms '), write(RedDoms), nl, %test
solutions(RedDoms,A),
write('Consistent Doms '), write(RedDoms), nl, %test
write('Consistent Arcs '), write(A), nl. %test
% consider(D0,D1,CA,TDA)
% D0 is the set of inital domains
% D1 is the set of reduced domains
% CA = consistent arcs,
% TDA = to do arcs
consider(D,D,_,[]).
consider(D0,D3,CA,[rel([X,Y],R)|TDA]) :-
choose(dom(XV,DX),D0,D1),X==XV,
% write('D0 '), write(D0),
% write('D1 '), write(D1), nl,
choose(dom(YV,DY),D1,_),Y==YV, !,
prune(X,DX,Y,DY,R,NDX),
( NDX = DX
->
consider(D0,D3,[rel([X,Y],R)|CA],TDA)
; acc_todo(X,Y,CA,CA1,TDA,TDA1),
consider([dom(X,NDX)|D1],D3,
[rel([X,Y],R)|CA1],TDA1)).
% prune(X,DX,Y,DY,R,NDX)
% variable X had domain DX
% variable Y has domain DY
% R is a relation on X and Y
% NDX = {X in DX | exists Y such that R(X,Y) is true}
prune(_,[],_,_,_,[]).
prune(X,[V|XD],Y,YD,R,XD1):-
\+ (X=V,member(Y,YD),R),!,
prune(X,XD,Y,YD,R,XD1).
prune(X,[V|XD],Y,YD,R,[V|XD1]):-
prune(X,XD,Y,YD,R,XD1).
% acc_todo(X,Y,CA,CA1,TDA,TDA1)
% given variables X and Y,
% updates consistent arcs from CA to CA1 and
% to do arcs from TDA to TDA1
acc_todo(_,_,[],[],TDA,TDA).
acc_todo(X,Y,[rel([U,V],R)|CA0],
[rel([U,V],R)|CA1],TDA0,TDA1) :-
( X \== V
; X == V,
Y == U),
acc_todo(X,Y,CA0,CA1,TDA0,TDA1).
acc_todo(X,Y,[rel([U,V],R)|CA0],
CA1,TDA0,[rel([U,V],R)|TDA1]) :-
X == V,
Y \== U,
acc_todo(X,Y,CA0,CA1,TDA0,TDA1).
% solutions(Doms,Arcs) given a reduced set of
% domains, Dome, and arcs Arcs, solves the CSP.
solutions(Doms,_) :-
solve_singletons(Doms),
write('Single Doms '), write(Doms), nl. %test
solutions(Doms,A) :-
my_select(dom(X,[XV1,XV2|XVs]),Doms,ODoms),
split([XV1,XV2|XVs],DX1,DX2),
acc_todo(X,_,A,CA,[],TDA),
( consistent([dom(X,DX1)|ODoms],CA,TDA,A)
; consistent([dom(X,DX2)|ODoms],CA,TDA,A)).
% solve_singletons(Doms) is true if Doms is a
% set of singletom domains, with the variables
% assigned to the unique values in the domain
solve_singletons([]).
solve_singletons([dom(X,[X])|Doms]) :-
solve_singletons(Doms).
% select(E,L,L1) selects the first element of
% L that matches E, with L1 being the remaining
% elements.
my_select(D,Doms,ODoms) :-
select(D,Doms,ODoms), !.
% choose(E,L,L1) chooses an element of
% L that matches E, with L1 being the remaining
% elements.
choose(D,Doms,ODoms) :-
select(D,Doms,ODoms).
% split(L,L1,L2) splits list L into two lists L1 and L2
% with the about same number of elements in each list.
split([],[],[]).
split([A],[A],[]).
split([A,B|R],[A|R1],[B|R2]) :-
split(R,R1,R2).
/* -------------------------------------------------------------------*/
cs1(V, V). %A1 = A2
cs2(V1, V2) :- (V1 is V2 - 1; V2 is V1 - 1). %next
cs3(V1, V2) :- V1 is V2 + 1. %right
zebra(English,Spaniard,Ukrainian,Norwegian,Japanese,
Red,Green,Ivory,Yellow,Blue,
Dog,Snails,Fox,Horse,Zebra,
Coffee,Tea,Milk,Orange_Juice,Water,
Old_Gold,Kools,Chesterfields,Lucky_Strike,Parliaments) :-
csp([dom(English, [1, 2, 3, 4, 5]),
dom(Spaniard, [1, 2, 3, 4, 5]),
dom(Ukrainian, [1, 2, 3, 4, 5]),
dom(Norwegian, [1, 2, 3, 4, 5]),
dom(Japanese, [1, 2, 3, 4, 5]),
dom(Red, [1, 2, 3, 4, 5]),
dom(Green, [1, 2, 3, 4, 5]),
dom(Ivory, [1, 2, 3, 4, 5]),
dom(Yellow, [1, 2, 3, 4, 5]),
dom(Blue, [1, 2, 3, 4, 5]),
dom(Dog, [1, 2, 3, 4, 5]),
dom(Snails, [1, 2, 3, 4, 5]),
dom(Fox, [1, 2, 3, 4, 5]),
dom(Horse, [1, 2, 3, 4, 5]),
dom(Zebra, [1, 2, 3, 4, 5]),
dom(Coffee, [1, 2, 3, 4, 5]),
dom(Tea, [1, 2, 3, 4, 5]),
dom(Milk, [1, 2, 3, 4, 5]),
dom(Orange_Juice, [1, 2, 3, 4, 5]),
dom(Water, [1, 2, 3, 4, 5]),
dom(Old_Gold, [1, 2, 3, 4, 5]),
dom(Kools, [1, 2, 3, 4, 5]),
dom(Chesterfields, [1, 2, 3, 4, 5]),
dom(Lucky_Strike, [1, 2, 3, 4, 5]),
dom(Parliaments, [1, 2, 3, 4, 5])],
[rel([English, Red], cs1(English,Red)),
rel([Spaniard, Dog], cs1(Spaniard,Dog)),
rel([Coffee, Green], cs1(Coffee,Green)),
rel([Ukrainian, Tea], cs1(Ukrainian,Tea)),
rel([Green, Ivory], cs3(Green,Ivory)),
rel([Old_Gold, Snails], cs1(Old_Gold,Snails)),
rel([Kools, Yellow], cs1(Kools,Yellow)),
rel([Milk, Milk], Milk = 3),
rel([Norwegian, Norwegian], Norwegian = 1), %here is the problem
rel([Chesterfields, Fox], cs2(Chesterfields,Fox)),
rel([Kools, Horse], cs2(Kools,Horse)),
rel([Lucky_Strike, Orange_juice], cs1(Lucky_Strike,Orange_juice)),
rel([Japanese, Parliaments], cs1(Japanese,Parliaments)),
rel([Norwegian, Blue], cs2(Norwegian,Blue))]).
