A prolog program that reflects people sitting at a

Question

I've got a prolog homework to do: There are 5 persons sitting at a round table of different nationalities (french, english, polish, italian, turkish). Each of them knows only one other language other than their own. They sit at the round table in such a way that each of them can talk with their 2 neighbors (with one neighbor they talk in their native tongue and with the other in the single foreign language they know). The english person knows italian, the polish person knows french, the turkish person doesn't know english. The question is what foreign language does the turkish person know?

I've done something using only clauses and predicates but I reached a dead end, teacher suggested the easiest way would be to use lists.

Any thoughts on what that list would contain or any code ideas at all?

UPDATE (weak logic code):

    predicates
knowTheLanguage(symbol,symbol)  
knowNotTheLanguage(symbol,symbol)
isNeighbor(symbol,symbol,symbol,symbol)

aTheory(symbol,symbol,symbol,symbol) 
anotherTheory(symbol,symbol,symbol,symbol)

    clauses
knowTheLanguage(englishman,italian).
knowTheLanguage(polishman,franch).

%native tongues
knowTheLanguage(englishman,english).
knowTheLanguage(frenchman,franch).
knowTheLanguage(polishman,polish).
knowTheLanguage(italianman,italian).
knowTheLanguage(turk,turkish).


knowNotTheLanguage(turk,english).

aTheory(centralPerson, languageCntrlPers, personOnOneSide,languagePrsnOnOneSide) if knowTheLanguage(personOnOneSide,languageCntrlPers)
                                                                            and not( knowTheLanguage(centralPerson,languagePrsnOnOneSide))
                                                                            and not(knowNotTheLanguage(centralPerson,languagePrsnOnOneSide)).
anotherTheory(centralPerson, languageCntrlPers, personOnOneSide,languagePrsnOnOneSide) if knowTheLanguage(centralPerson,languagePrsnOnOneSide) 
                                                                            and  not( knowTheLanguage(personOnOneSide,languageCntrlPers))
                                                                            and not(knowNotTheLanguage(centralPerson,languagePrsnOnOneSide)).

isNeighbor(centralPerson, languageCntrlPers, personOnOneSide,languagePrsnOnOneSide) if aTheory(centralPerson, languageCntrlPers, personOnOneSide,languagePrsnOnOneSide)
                                                                        or
                                                                        anotherTheory(centralPerson, languageCntrlPers, personOnOneSide,languagePrsnOnOneSide).

Update - programming environment : turbo prolog 2.0 '86,'88 by Borland, also I'm a complete beginer in prolog, so... I'd apreciate at least a full sketch of the program and explanations outside of the code body. I process things slow :D

Answer 1

Normally, I would solve such a puzzle using constraints, but that would probably be too advanced for your homework. So, instead of using constraints to restrict the search space, we have to use tests to check whether the solution is feasible.

You will need to work with two lists, say People and Languages. Each element of the lists corresponds to one seat at the table. Both lists can have the same domain, [f,e,p,i,t]. The semantics of the domain should be clear.

To generate the solution, you first set up the lists, then instantiate the lists and check whether the instantiation fulfils your constraints:

puzzle(People, Languages) :-
    Domain = [f,e,p,i,t],
    length(People, 5),
    length(Languages, 5),
    % symmetry break:
    People = [f|_],
    % instantiate People
    people(People, Domain),
    % instantiate languages and check constraints
    languages(Languages, People, Domain).

Note that the first element of list People is set to f. This is to rule out symmterical solutions, which will otherwise be returned since the table is round. Without this restriction, each solution would have four additional symmetrical solutions.

Try to come up with your own solution before reading on... :-)

The list People is instantiated first. We need to take care that each element appears only once:

people([], []) :- !.
people([P|RestP], Domain) :-
    delete(P, Domain, RestD),
    people(RestP, RestD).

Your dialect of Prolog may have select/3 instead of delete/3.

When instantiating the list Languages, we also check that the puzzle constraints are not violated:

languages(Languages, People, Domain) :-
    Term =.. [[]|People],
    languages0(Languages, People, Term, 1, Domain).
languages0([], _, _, _, _) :- !.
languages0([L|RestL], [P|RestP], Term, I, Domain) :-
    delete(L, Domain, RestD),
    L \= P, % language needs to be foreign
    check_l(P, L),
    check_n(L, I, Term),
    I1 is I+1,
    languages0(RestL, RestP, Term, I1, RestD).

Again, each element can only appear once.

check_l checks the constraints regarding the foreign languages:

check_l(e, i).
check_l(p, f).
check_l(t, L) :- L \= e.
check_l(f, _).
check_l(i, _).

check_n ensures that language and nationality of either left or right neighbour match:

check_n(L, I, Term) :-
    ( I == 1 -> NL = 5 ; NL is I-1 ),
    ( I == 5 -> NR = 1 ; NR is I+1 ),
    ( arg(NL, Term, L) ; arg(NR, Term, L) ).

There are two solutions:

?- puzzle(P, L).
P = [f, e, i, t, p]
L = [e, i, t, p, f]
Yes (0.00s cpu, solution 1, maybe more)
P = [f, p, t, i, e]
L = [e, f, p, t, i]
Yes (0.01s cpu, solution 2, maybe more)
No (0.01s cpu)

Answer 2

You can work with cyclic list, try this code to understand.

t :-
    L = [1,2,3 | L],
    my_write(5, L).

my_write(0, _).
my_write(N, [H | T]) :-
    write(H), nl,
    N1 is N - 1,
    my_write(N1, T).

Cyclic list may be very usefull for you.

Describe what are the elements of the list, then what is the constraint for the languages

EDIT : Here is my solution, works with SWI-Prolog :

% @arg1 : list of nationalities around the table
% @arg2 : list of persons
dinner(Languages, Table) :-
    length(Languages, Len),
    length(Table, Len),

    % set Natianalities and languages
    init_1(Table, Languages, Languages),

    % create cyclic list
    % works with SWI-Prolog
    append(Table, L, L),

    % set languages constraint
    init_2(Len, L).

init_1([], [], []).

init_1([person(N, L) | T], Nations, Languages):-
    select(N, Nations, New_Nations),

    % problem specific
    (   N = english
    ->  L = italian
    ;   N = polish
    ->  L = french
    ;   true),

    select(L, Languages, New_Languages),

    % problem specific
    (   N = turkish
    ->  L \=  english
    ;   true),

    init_1(T, New_Nations, New_Languages).

% persons speaks with theirs two neighbors
init_2(Tr, [person(_N1, L1), person(N2, L2), person(N3, L3) | T]) :-
    Tr > 0,
    member(N2, [L1, L3]),
    Tr1 is Tr - 1,
    init_2(Tr1, [person(N2, L2), person(N3, L3) | T]).

init_2(0, _).

Answer 3

Generally, when modelling a problem, it's important to identify a compact representation, eliminating irrelevant details. Here having, for instance, polishman and polish is useless. We can agree that polish stands for both the man and the language.

I sketch the solution, please fill in the ellipsis, adding the constraints:

puzzle(L) :-
    L = [P1,P2,P3,P4,P5],
    cadj(P5,P1,P2),
    ...
    member(p(english, italian), L),
    member(p(french,  _ ),      L),
    ...
    \+ member(p(turk, english), L).

% constrain adjacents
cadj(p(Pl, Ll), p(P, K), p(Pr, Lr)) :-
    P = Ll, K = Pr ; P = Lr, K = Pl.

p/2 stands for the man and the language he knows. cadj/3 says that if the man at left knowns my language, I must know the language of the man at right, or viceversa.

To get the required language, try

puzzle :-
    puzzle(L),
    memberchk(p(turk, T), L),
    writeln(T:L).

There are more solutions, but the language T is consistently constrained to a single value...