Prolog逻辑难题和约束规划

Question

我的家庭作业是在 prolog 中定义 10 个事实来解决这个难题。

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.

我已经定义了 8 个约束并将我的解决方案空间减少到 15 个。但是我不知道如何定义最后两个事实。

% 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=[_,_].

例如，我为事实 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).

这减少了解决方案空间，但之后它仍然包含不应在减少的解决方案集中的元素。

我正在使用这个函数来获取我的解决方案集大小

findall(_, solve(X), Solutions), length(Solutions,N).

这是解决方案集元素

solve(X).

我不知道如何描述这两个事实。如果有人可以提供帮助，我将不胜感激 :)。

对不起我的英语，它不是我的第一语言。

Answer 1

与您的不同的方法是使用具有有限域的约束编程构造(即 Prolog 的 clpfd 库)。这是这个问题的两个 MiniZinc 模型，它们可能会给您一些启发。由于这是作业，我什至不会尝试在“纯”Prolog 中解决它，即没有 clpfd。

这是一个使用集合数组的模型:http://hakank.org/minizinc/five_translators.mzn

同样的主要方法，但使用 0/1 矩阵代替:http://hakank.org/minizinc/five_translators.mzn

(我完全不确定这是否会对您有所帮助，但这是一个有趣的问题...)