Programming Holograms and Prolog Logic Constraints
I have my homework to identify 10 facts in the prologue in order to solve this puzzle.
Five translators are working in an international organization:
Spaniard, Englishman, Frenchman, German and Russian.
Each of them speaks its native language and also two
languages from the native languages of other translators. Find
the languages speaked by each translator if it is known that
1. The Englishman speaks German.
2. The Spaniard speaks French.
3. The German does not speak Spanish.
4. The Frenchman does not speak German.
5. Spaniard and Englishman can talk with each other in German.
6. Englishman and Frenchman can talk with each other in two
languages.
7. Four translators speak Russian.
8. Exactly two translators speak French.
9. Only one translator who speaks Spanish speaks also Russian.
10. Russian and Englishman have no common languages except
their native languages.
I've already defined 8 constraints and reduced the solution space to 15. But I don't know how to determine the last two facts.
% lahendusstruktuur
structure(
[translator(inglane,_,_,inglise),
translator(sakslane,_,_,saksa),
translator(hispaanlane,_,_,hispaania),
translator(prantslane,_,_,prantsuse),
translator(venelane,_,_,vene)]).
% abipredikaadid
nationality(translator(B,_,_,_),B).
language1( translator(_,B,_,_),B).
language2( translator(_,_,B,_),B).
native_language(
translator(_,_,_,B),B).
% keelte faktid (andmebaas)
possible_language(vene).
possible_language(inglise).
possible_language(hispaania).
possible_language(prantsuse).
possible_language(saksa).
% tabeli täitmine
solve(S):-
structure(S),
fill_structure(S),
fact1(S),
fact2(S),
fact3(S),
fact4(S),
fact5(S),
fact6(S),
fact7(S),
fact8(S),
%fact9(S),
%fact10(S),
true.
fill_structure([A,B,C,D,E]):-
fill_line(A,inglane),
fill_line(B,sakslane),
fill_line(C,hispaanlane),
fill_line(D,prantslane),
fill_line(E,venelane).
fill_line(X,Nationality):-
nationality(X,Nationality),
possible_language(Keel1),
language1(X,Keel1),
possible_language(Keel2),
language2(X,Keel2),
native_language(X,Native),
Keel1\=Native,
Keel2\=Native,
Keel1 @> Keel2.
% keelte generaator
speaks(Nationality,Language,S):-
member(X,S),
nationality(X,Nationality),
language(X,Language).
language(X,L):-native_language(X,L).
language(X,L):-language1(X,L).
language(X,L):-language2(X,L).
% faktid 1-10
%1. The Englishman speaks German.
fact1(X):-
speaks(inglane,saksa,X).
%2. The Spaniard speaks French.
fact2(X):-
speaks(hispaanlane,saksa,X).
%3. The German does not speak Spanish.
fact3(X):-
\+speaks(sakslane,hispaania,X).
% The Frenchman does not speak German.
fact4(X):-
\+speaks(prantslane,saksa,X).
% Spaniard and Englishman can talk with each other in German.
fact5(X):-
speaks(hispaanlane,saksa,X),
speaks(inglane,saksa,X).
%6. Englishman and Frenchman can talk with each other in two languages.
fact6(X):-
findall(Keel,
(
speaks(inglane,Keel,X),
speaks(prantslane,Keel,X)
),
Keelte_hulk),
Keelte_hulk=[_,_].
%% Four translators speak Russian.
fact7(X):-
findall(Inimene,
(
speaks(Inimene,vene,X),
speaks(Inimene,vene,X),
speaks(Inimene,vene,X),
speaks(Inimene,vene,X)),Inimeste_hulk),
Inimeste_hulk=[_,_,_,_].
/*
(speaks(inglane,vene,X),
speaks(sakslane, vene,X),
speaks(hispaanlane, vene,X),
\+ speaks(prantslane, vene,X));
(speaks(inglane,vene,X),
speaks(sakslane, vene,X),
\+speaks(hispaanlane, vene,X),
speaks(prantslane, vene,X));
(speaks(inglane,vene,X),
\+speaks(sakslane, vene,X),
speaks(hispaanlane, vene,X),
speaks(prantslane, vene,X));
(speaks(inglane,vene,X),
\+speaks(sakslane, vene,X),
speaks(hispaanlane, vene,X),
speaks(prantslane, vene,X)). */
%Exactly two translators speak French.
fact8(X):-
findall(Inimene,
(
speaks(Inimene,prantsuse,X),
speaks(Inimene,prantsuse,X)),Inimeste_hulk),
Inimeste_hulk=[_,_].
For example, I tried a solution like this for fact 10.
fact10(X):-
speaks(inglane,inglise,X), speaks(venelane,inglise,X),
speaks(venelane,inglise,X), speaks(venelane,vene,X),
\=(speaks(inglane,hispaania,X),speaks(venelane, hispaania,X),
\=(speaks(inglane,prantsuse,X),speaks(venelane, prantsuse,X),
\=(speaks(inglane,saksa,X),speaks(venelane,saksa,X).
This reduces the solution space, but after that it still contains elements that should not be in the given solution set.
I am using this function to get the size of a set of solutions
findall(_, solve(X), Solutions), length(Solutions,N).
And this is for the elements of the decision set
solve(X).
I have no idea how to describe these two facts. If anyone could help I would appreciate :).
Sorry for my English, this is not my first language.
source to share
Another approach from yours is to use finite domain constraint programming constructs (i.e. in the Prolog clpfd library). Here are two MiniZinc models of this problem that might give you some inspiration. Since this is homework, I won't even try to solve it in "pure" Prolog, that is, without clpfd.
Here's a model using an array of sets: http://hakank.org/minizinc/five_translators.mzn
And the same principled approach, but instead of using a 0/1 matrix: http://hakank.org/minizinc/five_translators.mzn
(I'm not sure if this will help you, but it's a fun problem ...)
source to share
I think this relationship will fix your rule 9 problem: http://www.swi-prolog.org/pldoc/man?predicate=bagof%2f3
Something like
bagof(Translator,(some condition, possibly with commas or semicolons in it,
verifying that Translator speaks those two languages),
Translators),
Bagof offer here
- identifies a variable (first argument) to represent what we are interested in
- sets the condition associated with this variable to be solved in any way Prolog can
- collects all variables for which this condition applies into a list (third argument)
Then you check that the list is 1 in length.
I don't want to do my homework for you, so I will not fill out the condition, but if you were looking for all the translators who have giraffes and drink vodka this would be
(has(Translator,giraffe),drinks(Translator,vodka))
bagof can also be used for condition 10.
source to share