[SWI-Prolog][Débutant] Programmation par contrainte

**alexglvr** · 12/10/2008, 21h39

Bonjour,

Afin de résoudre un problème, j'ai fait des recherches sur la programmation par contrainte. Je suis tombé sur Developpez.com et le cours de prolog.

Pourriez vous svp me donner un coup de main afin de résoudre mon pb?

Voici de quoi il s'agit.

J'ai 4 variables à déterminer.
Elles appartiennent à l'ensemble des nombres entiers compris entre 1 et 20.
Elles sont toutes différentes.

En plus de ça, j'ai une dizaine de contraintes du type:

1 ou 2 d'entre elles appartiennent à l'ensemble A
Minimum 1 d'entre elles appartient à l'ensemble B
...

Les ensembles A, B,.. sont des sous ensembles De [1,2,...20]

Le but est de trouver toutes les combinaisons répondant aux contraintes...

Ce genre de problème peut il est résolu avec swi-prolog?

Merci de votre aide,

Alexandre

**Alp** · 12/10/2008, 22h15

Oui c'est tout à fait possible.

Il faut fixer des contraintes du type :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

between_1_and_20(X) :- X =< 20, X >= 1.

Ensuite, il faut réfléchir un peu pour les contraintes

1 ou 2 d'entre elles appartiennent à l'ensemble A
Minimum 1 d'entre elles appartient à l'ensemble B
...

Tu peux tout à fait y arriver en travaillant avec le cours de Prolog à côté

**Trap D** · 13/10/2008, 12h55

Peux-tu donner un peu plus de détails et ce que tu as écrit.
La bibliothèque clpfd me semble être faite pour ça, mais il faut des détails ...

**gorgonite** · 13/10/2008, 13h31

attention tu seras peut-être obligé d'utiliser une bib pour les domaines finis suivant la complexité du problème... ce qui peut fortement ralentir la résolution

**alexglvr** · 13/10/2008, 19h00

Merci de vos réponses!

j'ai commencé à lire les cours... Mais ce n'est pas simple.
Demain j'installe swi-prolog et je vais essayé de faire le début du programme en utilisant les exemples du site.

Voici un exemple concret du problème:

J'ai 4 variables à déterminer.
Elles appartiennent à l'ensemble des nombres entiers compris entre 1 et 20.
Elles sont toutes différentes.

- 2,3 ou 4 de ces variables appartiennent à [1,2,3,4,5,6,7,8,12,15,17,18,20]
- 2,3,ou 4 de ces variables appartiennent à [1,2,3,4,5,6,8,12,15,17,18,20]
- 1,2,3 ou 4 de ces variables appartiennent à [1,2,3,4,6,8,12,15,17,18]
- 0,1 ou 2 de ces variables appartiennent à [1,2,3,4,6,8,15,17,18]
- ...

Quels Combinaisons répondent à ces critères?

NB: Les contraintes changent pour chaque études, mais reste de la même forme...

Tout le début ne semble pas poser problème. Mais comment définir ce type de contraintes?

Alex

**alexglvr** · 14/10/2008, 14h40

Swi-prolog installé et j'ai testé quelques exemples présents dans les cours. Tout fonctionne.

J'ai lu plusieurs des cours, mais des choses restent incomprises...

Je vais essayé de comprendre...

Alex

**Alp** · 15/10/2008, 11h50

Pose les questions ! On va essayer d'y répondre.

Qu'est-ce que tu ne comprends pas ?

**alexglvr** · 16/10/2008, 17h15

j'ai beaucoup de mal avec la syntax... Certains exemples ça va, d'autres c'est le néant... (tous les exemples de 'programmation prolog' par exemple, je n'y comprends rien du tout)

Une fois ceci maitriser, il faut pourvoir aborder le problème à résoudre sous le bon angle... Et la encore ça ne va pas être gagné...

C'est la première fois qu'un langage de prog me pose problème...

Y a t il un autre logiciel que prolog pour la programmation par contrainte?

**Alp** · 16/10/2008, 18h38

Pourquoi ne pas nous poser les questions sur les choses que tu ne comprends pas ?

Et ensuite, on pourra discuter ensemble de la vision à adopter du problème pour le résoudre !

**Trap D** · 16/10/2008, 21h55

Bonjour

J'ai un peu réfléchit à ton problème et je pense avoir un début de solution. Ce n'est pas optimisé, mais pour le moment ça déblaie le terrain.
Le début du code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
tuple_possible( [Y1,Y2,Y3,Y4]) :-
        % je définis les différents ensembles
	E0 = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20],
	E1 = [1,2,3,4,5,6,7,8,12,15,17,18,20],
	E2 = [1,2,3,4,5,6,8,12,15,17,18,20],
	E3 = [1,2,3,4,6,8,12,15,17,18],
	E4 = [1,2,3,4,6,8,15,17,18],
 
       % les 4 variables sont comprises entre 1 et 20
	member(Y1,E0),
	member(Y2,E0),
	member(Y3,E0),
	member(Y4,E0),
 
      % Elles sont toutes différentes
      % Pour éviter les solutions multiples, autant les ranger
	Y1 < Y2, Y2 < Y3, Y3 < Y4,

Tu désires avoir

2,3 ou 4 de ces variables appartiennent à [1,2,3,4,5,6,7,8,12,15,17,18,20] (la liste E1)

Celà signifie que au moins 2 de ces variables sont dans E1. Donc, on peut avoir

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
	(   (member(Y1, E1), member(Y2, E1)); 
	    (member(Y1, E1), member(Y3, E1));
	    (member(Y1, E1), member(Y4, E1));
	    (member(Y2, E1), member(Y3, E1));
	    (member(Y2, E1), member(Y4, E1));
	    (member(Y3, E1), member(Y4, E1))),

Y1 et Y2 sont membre de E1, ou Y1 et Y3 sont membres de E1 ou ...
Dés que le "ou" est vérifié, on s'arrête, il peut y avoir d'autres éléments dans E1, on n'en a cure.

J'espère que celà va t'aider, je te laisse chercher la codification des autres conditions.

Bon courage

**alexglvr** · 17/10/2008, 09h35

Merci Trad pour ton code, ça m'aide bien a comprendre...

Alp, j'ai pas eu beaucoup de temps ces derniers jours pour exposer ce que je ne comprends pas.

Je vais essayer de le faire, le plus clairement possible.

prenons l'exemple suivant (cf. Programmation Prolog de pcaboche, cours sur les pattern):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
% Elimination des cas d'erreur
genereListeZeros(N, _) :-     % Cas N<0
  N<0,  !, fail. 
 
% Execution dirigée
genereListeZeros(N, []) :-    % Cas N=0
  N==0,
  !.
 
genereListeZeros(N, [0|Q]) :-   % Les autres cas (N>0)
  !,
  N1 is N-1,
  genereListeZeros(N1, Q).

Je vois bien le traitement des différents cas, par contre, je n'explique pas:
- l'utilisation de _ ligne 2

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

genereListeZeros(N, _)

- l'utilisation de [] ligne 6

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

genereListeZeros(N, [])

- l'utilisation de [0|Q] et Q dans la dernière instance de genereListeZeros.

Je vois bien l'idée de récursivité du programme (N1=N-1), mais ne comprends pas ce qu'il fait...

Je comprends l'utilisation du Fail, mais pas du cut (!)...

Si on continue sur le cours sur les patterns, je comprends bien les différentes structures de programme et leur rôle. Par contre je n'arrive pas à comprendre les deux codes sources suivant ....

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
enum(X, [T|_], (X,T) ).
enum(X, [_|Q], R) :- enum(X, Q, R).

et

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
%%
% Retourne les combinaisons une par une
%
combi([L|Q], [Elem|R]) :-
  member(Elem, L),
  combi(Q, R).
 
combi([], []).
 
 
 
%%
% Retourne la liste de toutes les combinaisons
%
combinaisons(Listes, Combis) :-
  findall(C, combi(Listes, C), Combis).

peut être on va déjà commencer avec ça...

Je te prépare la suite...

Merci de votre aide

Alex

**Trap D** · 17/10/2008, 10h56

Ce que je te propose, c'est que tu termines ton programme en Prolog pur, et je te montrerais ensuite comment le transformer en utilisant la bibliothèque de programation avec contraintes clpfd.
J'ai réussi à le faire, (grâce à une aide appréciable de Markus Triska) et tu verras l'amélioration spectaculaire des performances.

Je n'ai malheureusement pas le temps tout de suite de t'aider pour tes problèmes sur les tutos du site

**alexglvr** · 18/10/2008, 16h54

J'ai avancé le programmes avec les autres contraintes... Par contre, j'ai plusieurs questions:

Tout d'abord, voila ce que j'ai écrit:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
tuple_possible( [Y1,Y2,Y3,Y4]) :-
        % je définis les différents ensembles
	E0 = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20],
	E1 = [1,2,3,4,5,6,7,8,12,15,17,18,20],
	E2 = [1,2,3,4,5,6,8,12,15,17,18,20],
	E3 = [1,2,3,4,6,8,12,15,17,18],
	E4 = [1,2,3,4,6,8,15,17,18],
 
       % les 4 variables sont comprises entre 1 et 20
	member(Y1,E0),
	member(Y2,E0),
	member(Y3,E0),
	member(Y4,E0),
 
      % Elles sont toutes différentes
      % Pour éviter les solutions multiples, autant les ranger
	Y1 < Y2, Y2 < Y3, Y3 < Y4,
 
	(   (member(Y1, E1), member(Y2, E1)); 
	    (member(Y1, E1), member(Y3, E1));
	    (member(Y1, E1), member(Y4, E1));
	    (member(Y2, E1), member(Y3, E1));
	    (member(Y2, E1), member(Y4, E1));
	    (member(Y3, E1), member(Y4, E1))),
 
	(   (member(Y1, E2), member(Y2, E2)); 
	    (member(Y1, E2), member(Y3, E2));
	    (member(Y1, E2), member(Y4, E2));
	    (member(Y2, E2), member(Y3, E2));
	    (member(Y2, E2), member(Y4, E2));
	    (member(Y3, E2), member(Y4, E2))),
 
	(   member(Y1, E3);
	    member(Y2, E3); 
	    member(Y3, E3);
	    member(Y4, E3)),

Questions:

- La dernière contrainte :
(0,1 ou 2 de ces variables appartiennent à E4), je ne voyais pas comment la coder (sans la transformer en 2, 3 ou 4 appartiennent à E0-E4) ???

- Quand tu dis :

Tu désires avoir
Citation:
2,3 ou 4 de ces variables appartiennent à [1,2,3,4,5,6,7,8,12,15,17,18,20] (la liste E1)
Celà signifie que au moins 2 de ces variables sont dans E1. Donc, on peut avoir
Code :

( (member(Y1, E1), member(Y2, E1));
(member(Y1, E1), member(Y3, E1));
(member(Y1, E1), member(Y4, E1));
(member(Y2, E1), member(Y3, E1));
(member(Y2, E1), member(Y4, E1));
(member(Y3, E1), member(Y4, E1))),

Y1 et Y2 sont membre de E1, ou Y1 et Y3 sont membres de E1 ou ...
Dés que le "ou" est vérifié, on s'arrête, il peut y avoir d'autres éléments dans E1, on n'en a cure.

je suis d'accord, mais est ce qu'après on pourras quand même citer toutes les solutions possibles??? Il ne traitera pas les cas 3 vars ou 4 vars appartiennent à E1? si???

- Pour compliquer un peu, comment écrirais tu alors 2 ou 3 vars appartiennent à E1???

- plus généralement sur le prolog, Si des contraintes sont partiellement ou complètement redondantes ou si l'intersection de deux contraintes fait apparaitre des infos, est ce nécessaire de le spécifier dans la programmation, ou Prolog se débrouille tout seul???

- Je voudrais ajouter la contrainte "Maximum 2 de ces variables peuvent avoir des valeurs consécutives" ?
- il faudrait aussi un décompte des combinaisons possibles ainsi qu'une liste de ces dernières. J'ai vu une commande findall, mais ne sais comment l'utiliser dans notre situation...

Désolé pour ce grand nombre de questions...

Merci encore de ton aide,

Alex

**Trap D** · 18/10/2008, 18h33

Début de réponse :

- La dernière contrainte :
(0,1 ou 2 de ces variables appartiennent à E4), je ne voyais pas comment la coder (sans la transformer en 2, 3 ou 4 appartiennent à E0-E4) ???

Celà veut dire en fait qu'au moins 2 des variables n'appartiennent pas à E4 !

je suis d'accord, mais est ce qu'après on pourras quand même citer toutes les solutions possibles??? Il ne traitera pas les cas 3 vars ou 4 vars appartiennent à E1? si???

Si car dès que le test X1 et X2 appartiennent à E1, il passe à lma suite et choisit les valeurs de X3 et X4 n'importe ou dans E0 (donc eventuellement dans E1, en appliquant simplement X2 < X3 < X4, (c'est moi qui ait imposé celà, peutêtre que tu ne le voulais pas, c'est pour avoir moins de solutions).

- plus généralement sur le prolog, Si des contraintes sont partiellement ou complètement redondantes ou si l'intersection de deux contraintes fait apparaitre des infos, est ce nécessaire de le spécifier dans la programmation, ou Prolog se débrouille tout seul???

Prolog se débrouille tout seul.

Je voudrais ajouter la contrainte "Maximum 2 de ces variables peuvent avoir des valeurs consécutives" ?

X2-X1 = 1 ou ...

- Pour compliquer un peu, comment écrirais tu alors 2 ou 3 vars appartiennent à E1???

Pas trouvé de réponses pour le moment je chercherais tout à l'heure

- il faudrait aussi un décompte des combinaisons possibles ainsi qu'une liste de ces dernières. J'ai vu une commande findall, mais ne sais comment l'utiliser dans notre situation...

J'ai appelé tuple_possible le prédicat qui en calcule 1.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
test :-
	setof(Vars, tuple_possible(Vars), L),
	length(L, N),
	writeln(N).

te donne la liste sans doublons, et length la longueur de la liste.

**Trap D** · 19/10/2008, 00h45

- Pour compliquer un peu, comment écrirais tu alors 2 ou 3 vars appartiennent à E1???

Un peu de réflexion, et on trouve...
Il suffit de forcer 2 variables dans E1 et en interdire 4 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
	% X1 est dans E1 et X2 ou X3 ou X4 y est aussi
	(
            (member(X1,E1), (member(X2,E1);member(X3,E1); member(X4,E1)));
	% ou X2 est dans E1 et X3 ou X4 y est aussi
	    (member(X2,E1), (member(X3,E1); member(X4,E1)));
	% ou ce sont X3 et X4 qui y sont
	    (member(X3,E1), member(X4, E1))
        ),
	% mais il faut interdire que tous les 4 y soient !!!
	\+((member(X1,E1), member(X2,E1), member(X3,E1), member(X4,1))),

Tu verras qu'avec la bibliothèque clpfd celà s'écrit de manière très élégante.

**alexglvr** · 19/10/2008, 12h45

Bonjour,

Voila le code avec toutes les contraintes:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
tuple_possible( [Y1,Y2,Y3,Y4]) :-
        % je définis les différents ensembles
	E0 = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20],
	E1 = [1,2,3,4,5,6,7,8,12,15,17,18,20],
	E2 = [1,2,3,4,5,6,8,12,15,17,18,20],
	E3 = [1,2,3,4,6,8,12,15,17,18],
	E4 = [1,2,3,4,6,8,15,17,18],
 
       % les 4 variables sont comprises entre 1 et 20
	member(Y1,E0),
	member(Y2,E0),
	member(Y3,E0),
	member(Y4,E0),
 
      % Elles sont toutes différentes
      % Pour éviter les solutions multiples, autant les ranger
	Y1 < Y2, Y2 < Y3, Y3 < Y4,
 
	(   (member(Y1, E1), member(Y2, E1)); 
	    (member(Y1, E1), member(Y3, E1));
	    (member(Y1, E1), member(Y4, E1));
	    (member(Y2, E1), member(Y3, E1));
	    (member(Y2, E1), member(Y4, E1));
	    (member(Y3, E1), member(Y4, E1))),
 
	(   (member(Y1, E2), member(Y2, E2)); 
	    (member(Y1, E2), member(Y3, E2));
	    (member(Y1, E2), member(Y4, E2));
	    (member(Y2, E2), member(Y3, E2));
	    (member(Y2, E2), member(Y4, E2));
	    (member(Y3, E2), member(Y4, E2))),
 
	(   member(Y1, E3);
	    member(Y2, E3); 
	    member(Y3, E3);
	    member(Y4, E3)),
 
	% au moins deux n'appartiennent pas à E4
 
	(   (\+(member(Y1,E4)), \+(member(Y2,E4))); 
	    (\+(member(Y1,E4)), \+(member(Y3,E4))); 
	    (\+(member(Y1,E4)), \+(member(Y4,E4))); 
	    (\+(member(Y2,E4)), \+(member(Y3,E4)));
	    (\+(member(Y2,E4)), \+(member(Y4,E4))); 
	    (\+(member(Y3,E4)), \+(member(Y4,E4)))),
 
	% au maximum 2 consecutifs
 
	(   ((Y2-Y1==1), (Y3-Y2/=1), (Y4-Y3/=1));
	    ((Y2-Y1/=1), (Y3-Y2==1), (Y4-Y3/=1));
	    ((Y2-Y1/=1), (Y3-Y2/=1), (Y4-Y3==1));
	    ((Y2-Y1/=1), (Y3-Y2/=1), (Y4-Y3/=1))).
 
test :-
	setof(Vars, tuple_possible(Vars), L),
	length(L, N),
	writeln(N).

par contre, à la compilation j'ai une erreur sur la contrainte au maximum 2 consécutifs...

J'ai testé le programme sans cette contrainte. Ça fonctionne.

Par contre :

- l'exécution de test donne le nombre de solution du problème mais ne cite pas les combinaisons, j'ai donc modifié la fin:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
test :-
	setof(Vars, tuple_possible(Vars), L),
	length(L, N),
	writeln(N),
        writeln(L).

- j'ai essayé d'utiliser findall à la place de setof. Le nombre de résultats passe de 3025 à 52209... Quelle est la différence entre setof et findall?

Si on revient à la contrainte Y1<Y2<Y3<Y4. tu dis dans ton dernier message que tu l'a ajouté pour diminuer le nombre de solutions... Si je me trompe pas, en plus de faire en sorte que Y1, Y2, Y3 et Y4 soient différentes, ça permet de travailler sur des combinaisons et non des arrangements. c'est ça?

Merci,

Alex

**Trap D** · 19/10/2008, 14h38

Euh, je t'ai dis une belle co****rie, c'est "1 is X2-X1" et pas X2-X1 = 1

Pour bagof et setof, l'excellent tuto de pcaboche t'expliquera tout.

Si je me trompe pas, en plus de faire en sorte que Y1, Y2, Y3 et Y4 soient différentes, ça permet de travailler sur des combinaisons et non des arrangements. c'est ça?

Oui c'est ça et ça dépend aussi de ton problème.

**alexglvr** · 19/10/2008, 14h53

voila la version corrigée:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
tuple_possible( [Y1,Y2,Y3,Y4]) :-
        % je définis les différents ensembles
	E0 = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20],
	E1 = [1,2,3,4,5,6,7,8,12,15,17,18,20],
	E2 = [1,2,3,4,5,6,8,12,15,17,18,20],
	E3 = [1,2,3,4,6,8,12,15,17,18],
	E4 = [1,2,3,4,6,8,15,17,18],
 
       % les 4 variables sont comprises entre 1 et 20
	member(Y1,E0),
	member(Y2,E0),
	member(Y3,E0),
	member(Y4,E0),
 
      % Elles sont toutes différentes
      % Pour éviter les solutions multiples, autant les ranger
	Y1 < Y2, Y2 < Y3, Y3 < Y4,
 
	(   (member(Y1, E1), member(Y2, E1)); 
	    (member(Y1, E1), member(Y3, E1));
	    (member(Y1, E1), member(Y4, E1));
	    (member(Y2, E1), member(Y3, E1));
	    (member(Y2, E1), member(Y4, E1));
	    (member(Y3, E1), member(Y4, E1))),
 
	(   (member(Y1, E2), member(Y2, E2)); 
	    (member(Y1, E2), member(Y3, E2));
	    (member(Y1, E2), member(Y4, E2));
	    (member(Y2, E2), member(Y3, E2));
	    (member(Y2, E2), member(Y4, E2));
	    (member(Y3, E2), member(Y4, E2))),
 
	(   member(Y1, E3);
	    member(Y2, E3); 
	    member(Y3, E3);
	    member(Y4, E3)),
 
	% au moins deux n'appartiennent pas à E4
 
	(   (\+(member(Y1,E4)), \+(member(Y2,E4))); 
	    (\+(member(Y1,E4)), \+(member(Y3,E4))); 
	    (\+(member(Y1,E4)), \+(member(Y4,E4))); 
	    (\+(member(Y2,E4)), \+(member(Y3,E4)));
	    (\+(member(Y2,E4)), \+(member(Y4,E4))); 
	    (\+(member(Y3,E4)), \+(member(Y4,E4)))),
 
	% au maximum 2 consecutifs
 
	(   ((1 is Y2-Y1), \+(1 is Y3-Y2), \+(1 is Y4-Y3));
	    (\+(1 is Y2-Y1), (1 is Y3-Y2), \+(1 is Y4-Y3));
	    (\+(1 is Y2-Y1), \+(1 is Y3-Y2), (1 is Y4-Y3));
	    (\+(1 is Y2-Y1), \+(1 is Y3-Y2), \+(1 is Y4-Y3))).
 
 
 
test :-
	setof(Vars, tuple_possible(Vars), L),
	length(L, N),
	%writeln(L),
	writeln(N).

Y vois tu des erreurs ou maladresses???

Ça donne quoi avec la librairie clpfd?

**alexglvr** · 19/10/2008, 18h57

j'ai fait un test sur un cas réel...

ça compile, ça tourne et puis
J'obtiens une erreur :"out of global stack" !!!

**Trap D** · 19/10/2008, 19h42

Pour au maximum 2 consécutifs, j' aurais fait ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
	% au maximum 2 consécutifs
 
	(X4-X2 > 2, X3-X1 > 2),

Pour ce qui est de la prgrammation par contraintes, je te donne le code.
Le # indique que la condition (par exemple #<) doit être considérée dans le cadre d'une contrainte

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
:- use_module(library(clpfd)).
tuple_possible3(Vars) :-
           % définition des différents ensembles
	   E0 = 1..20,
           E1 = 1..8\/12\/15\/17..18\/20,
           E2 = 1..6\/8\/12\/15\/17..18\/20,
           E3 = 1..4\/6\/8\/12\/15\/17..18,
           E4 = 1..4\/6\/8\/15\/17..18,
 
           Vars = [Y1,Y2,Y3,Y4],
           Vars ins E0,
 
           Y1 #< Y2, Y2 #< Y3, Y3 #< Y4,
 
	   % at least 2 of them are in E1
           Y1 in E1 #<==> A1, Y2 in E1 #<==> A2,
           Y3 in E1 #<==> A3, Y4 in E1 #<==> A4,
           A1+A2+A3+A4 #>= 2,
 
           % at least 2 of them are in E2
           Y1 in E2 #<==> B1, Y2 in E2 #<==> B2,
           Y3 in E2 #<==> B3, Y4 in E2 #<==> B4,
           B1+B2+B3+B4 #>= 2,
 
           % at least 1 of them is in E3
           Y1 in E3 #\/ Y2 in E3 #\/ Y3 in E3 #\/ Y4 in E3,
 
           % at least 2 of them are not in E4
           #\ Y1 in E4 #<==> C1, #\ Y2 in E4 #<==> C2,
           #\ Y3 in E4 #<==> C3, #\ Y4 in E4 #<==> C4,
           C1+C2+C3+C4 #>= 2,
 
           label(Vars).
 
test :-
	time(setof(Vars3, tuple_possible3(Vars3), L3)),
	length(L3, N3),
	writeln(N3).

Je suis désolé, je n'ai pas le temps tout de suite de le commenter.
L'aide Prolog s'obtient, dans la fenêtre du Prompt, par Help/online manual... et tu tapes par exemple #< dans le champ de saisie du bas.

Bon courage !

[SWI-Prolog][Débutant] Programmation par contrainte

Prolog

Discussions similaires

Partager

Partager