###### tags: `prolog`
# TP Prolog - s11 - ISC IL 3a
## Baudin Valentin et Braillard Simon
## Exercice 1
### a) Donner les nouveaux domaines de valeurs de chaque variable après propagation (consistance aux limites) dans l'exemple ci-contre, puis vérifier sur machine.
| Variable| Domaine initial | Contrainte traitée | Domaine après propagation |
|---|---|---|---|
| X | [1..5] | X #= Z - 2*Y | [1..3] |
| Y | [1..10] | Y #= (Z-X)/2 | [1..2] |
| Z | [0..5] | X+2*Y #= Z | [3..5] |
#### Solution
```json!
| ?- > ex1a.
X: _#0(1..3)
Y: _#17(1..2)
Z: _#34(3..5)asdvfasdfcasdfasdfasdfasdfasdjhfbakjsdhgfajszdgfakszdgfkauzsdgfkajshdgfakjshdgfkajshdgfakjshdfvaskd
(1 ms) yes
```
### b) Effectuer à la main sur le résultat (a) la distribution (et propagation automatique) selon le critère "first-fail" (c'est-à-dire en commençant par la variable qui a le plus petit domaine).
## Exercice 2
### a)
```prolog=
%--- apart(#X, #Y, #N) : X and Y are separated by an offset of at least N
apart(X, Y, N) :- (X+N #=< Y) #\/ (Y+N #=< X).
apart2(X, Y, N) :- X #< Y, X+N #=< Y.
apart2(X, Y, N) :- X #> Y, Y+N #=< X.
apart3(X, Y, N) :- (X - Y) * (X - Y) #>= N*N.
apart4(X, Y, N) :- (X #< Y #/\ X+N #=< Y) #\/ (X #> Y #/\ Y+N #=< X).
```
#### Output
Avec 15 :
```raw=
| ?- > apartBenchmark(15, apart).
(1 ms) yes
| ?- > apartBenchmark(15, apart2).
(10705 ms) yes
| ?- > apartBenchmark(15, apart3).
(4 ms) yes
| ?- > apartBenchmark(15, apart4).
(1 ms) yes
```
On voit que le apart2 qui fait du backtracking prend déjà beaucoup de temps avec un benchmark à 15, donc on va arrêter de tester pour la suite à 50 et à 100.
Avec 50:
```raw=
| ?- > apartBenchmark(50, apart).
(7 ms) yes
| ?- > apartBenchmark(50, apart3).
(131 ms) yes
| ?- > apartBenchmark(50, apart4).
(8 ms) yes
```
Avec 100:
```raw=
| ?- > apartBenchmark(100, apart).
(41 ms) yes
| ?- > apartBenchmark(100, apart3).
(1973 ms) yes
| ?- > apartBenchmark(100, apart4).
(82 ms) yes
```
Nous avons également essayé avec 150 mais nous obtenons un stack overflow.
### b)
Comme nous devons n'utiliser que des entiers naturels, on passe le domaine de 0 à 10 au lieu de -5 à 5, et on corrige le calcul
```prolog=
ex2b(A1, B1, C1) :-
fd_domain([A, B, C], 0, 10),
apart(A, B, 3),
apart(B, C, 3),
apart(C, A, 3),
9*(A-5) + 8*(B-5) + 4*(C-5) #= 0,
fd_labeling([A, B, C]),
A1 is A-5,
B1 is B-5,
C1 is C-5.
```
#### Output
```
| ?- > ex2b(A, B, C).
A = -4
B = 2
C = 5 ?
```
## Exercice 3
### Version naïve 1
### Version naïve 2
### Version affinée
### Version triplets primitifs
On peut voir que la version avec les triplets primitifs est très efficace. Cependant, lorsque notre domaine dépasse 1290 on ne trouve plus de solutions. C'est peut-être lié à un problème d'overflow.
## Exercice 4
```prolog=
ex4(A, B, C, D, E, F, G, H, I) :-
fd_domain([A, B, C, D, E, F, G, H, I], 1, 9),
fd_all_different([A, B, C, D, E, F, G, H, I]),
BC #= 10*B+C,
EF #= 10*E+F,
HI #= 10*H+I,
A*EF*HI + D*BC*HI + G*BC*EF #= 1*BC*EF*HI,
fd_labelingff([A, B, C, D, E, F, G, H, I, BC, EF, HI]),
write(A), write('/'), write(BC), write(' + '),
write(D), write('/'), write(EF), write(' + '),
write(G), write('/'), write(HI), write(' = 1'), nl.
```
### Output
```
| ?- > ex4(A, B, C, D, E, F, G, H, I).
5/34 + 7/68 + 9/12 = 1
A = 5
B = 3
C = 4
D = 7
E = 6
F = 8
G = 9
H = 1
I = 2 ? >
(13 ms) yes
```
### Casser la simétrie:
On voit que A/BC pourrait prendres les valeurs de D/EF et invérsément, il y a donc une simétrie. Pour casser cette simétrie, on peut ajouter des contraintes pour que A/BC soit plus petit ou égal que D/EF etc... On ajoute aussi la variable rendondante que A/BC <= 1/3.
```prolog=
ex4(A, B, C, D, E, F, G, H, I) :-
fd_domain([A, B, C, D, E, F, G, H, I], 1, 9),
fd_all_different([A, B, C, D, E, F, G, H, I]),
BC #= 10*B+C,
EF #= 10*E+F,
HI #= 10*H+I,
A*EF*HI #=< D*BC*HI,
D*BC*HI #=< G*EF*BC,
A*3 #=< BC*1,
A*EF*HI + D*BC*HI + G*BC*EF #= 1*BC*EF*HI,
fd_labelingff([A, B, C, D, E, F, G, H, I, BC, EF, HI]),
write(A), write('/'), write(BC), write(' + '),
write(D), write('/'), write(EF), write(' + '),
write(G), write('/'), write(HI), write(' = 1'), nl.
```
### Output:
```raw=
| ?- > ex4(A, B, C, D, E, F, G, H, I).
7/68 + 5/34 + 9/12 = 1
A = 7
B = 6
C = 8
D = 5
E = 3
F = 4
G = 9
H = 1
I = 2 ? >
```
Et c'est donc la seule solution possible alors qu'au paravant, on pouvait avoir plusieurs solutions (6) à cause de la simétrie.
### Comparaison des résultats avec le benchmark
`benchmark(150, ex4(A, B, C, D, E, F, G, H, I))` On lance donc le benchmark avec comme paramètre 150.
Résultat sans contraintes: 6088 ms
Résultat avec contraintes: 5110 ms
On a donc un gain de ~16%.
## Exercice 5
```prolog=
ex5(X, Y) :-
fd_domain([X, Y], 0, 4000),
6*X + 4*Y #=< 24000,
X + 2*Y #=< 6000,
-X + Y #=< 1000,
5*X + 4*Y #>= 0,
Z #= 5*X + 4*Y,
fd_maximize(fd_labelingff([X, Y]), Z),
X1 is X/1000.0, Y1 is Y/1000.0,
write('x = '), write(X1), nl,
write('y = '), write(Y1), nl.
```
### Output
```
| ?- > ex5(X, Y).
x = 3.0
y = 1.5
X = 3000
Y = 1500
(18 ms) yes
```
## Exercice 6
```prolog=
% ------------------------------------------------------------
%---- projSolve(+Prefs, +Prjs, ?Attrib, ?Cost, +OptMethod)
% OptMethod is either min
% or below(N)
projSolve(Prefs, Prjs, Attrib, Cost, OptMethod) :-
mismatch(Prefs, Attrib, Cost),
checkOcc(Prjs, Attrib),
projLabeling(Attrib, Cost, OptMethod).
% ------------------------------------------------------------
%---- projLabeling(?Attrib, ?Cost, +OptMethod) : performs "distribution" to...
% ...find the best Cost if OptMethod=min
% ...or find a Cost < N if OptMethod=below(N)
projLabeling(Attrib, Cost, min):-
fd_minimize(fd_labelingff(Attrib),Cost).
projLabeling(Attrib, Cost, below(N)) :-
Cost #< N,
fd_labelingff(Attrib).
% ------------------------------------------------------------
%---- checkOcc(+Prjs, #Attrib) : constrain the attribution to respect
% min/max nb of students per project
checkOcc([],_).
checkOcc([e(Proj,Min,Max)|Prjs],Attrib) :-
fd_atleast(Min, Attrib, Proj),
fd_atmost(Max, Attrib, Proj),
checkOcc(Prjs, Attrib).
% ------------------------------------------------------------
%---- mismatch(+Prefs, #Attrib, #Cost) : evaluate the total "cost" of
% the allocation
mismatch([], [], 0).
mismatch([P|Prefs], [A|Attrib], Cost) :-
fd_element(Rank, P, A),
mismatchOne(Rank, NewCost),
mismatch(Prefs, Attrib, AccCost),
Cost #= NewCost + AccCost.
% ------------------------------------------------------------
%---- mismatchOne(#Rank, #Cost) : evaluate the "cost" of allocating
% the Rank'th choice in preference list
% (the function may be changed...)
mismatchOne(Rank, Cost) :-
Cost #= (Rank - 1) * (Rank - 1).
```
### Output
Résultats sur MacOS
```
| ?- > go.
Prefs: [[11,7,1,8,3,6,10,9,5,4,2,12],[7,4,11,1,9,10,8,5,6,3,2,12],
[6,7,8,1,2,11,3,5,4,12,9,10],[12,6,11,2,8,4,5,9,3,7,1,10],
[11,2,8,10,12,6,5,1,7,4,9,3],[2,9,10,11,12,4,6,8,3,7,1,5],
[10,2,11,3,4,8,7,6,5,9,1,12],[5,3,11,9,6,1,4,10,12,8,7,2],
[2,9,8,1,11,12,4,7,10,3,5,6],[12,2,3,1,6,9,5,8,4,10,11,7],
[7,3,9,6,5,8,1,10,12,4,2,11],[12,11,7,5,10,1,3,2,9,8,6,4],
[11,10,2,1,4,8,9,5,6,12,7,3],[3,5,2,9,4,1,10,8,12,7,11,6],
[10,11,12,3,7,4,1,6,5,9,2,8],[1,5,7,10,9,4,8,3,2,12,6,11],
[3,11,5,7,6,10,1,8,9,12,2,4],[7,1,8,3,9,4,12,10,2,6,5,11]]
Attrib: [11,4,6,6,11,2,10,5,2,12,7,12,4,3,10,1,3,7]
Cost: 18
true ? >
(581 ms) yes
```
## Exercice 7
Pour cet exercice, nous avons eu besoin de l'aide de la classe pour le compréhension et la réalisation de cet exercice.
Le `max_one_elt`et le `exactly_one_elt` servent de contraintes. Le premier est pour les diagonales qui peuvent contenir 0 ou 1 reine. Le second les lignes et colonnes qui doivent contenir exactement 1 reine.
```prolog=
test_ex7(N):-
matrix_create(N, N, M),
matrix_values(M, V),
fd_domain_bool(V),
fd_exactly(N, V, 1),
matrix_transpose(M, Mt),
exactly_one_elt(M),
exactly_one_elt(Mt),
matrix_diagonals(M, Md),
max_one_elt(Md),
fd_labeling(V,[variable_method(random),value_method(max)]),
matrix_show(M).
max_one_elt([]).
max_one_elt([L|Ls]):-
fd_atmost(1, L, 1),
max_one_elt(Ls).
exactly_one_elt([]).
exactly_one_elt([L|Ls]):-
fd_exactly(1, L, 1),
exactly_one_elt(Ls).
```
### Solution
```
| ?- > test_ex7(8).
00010000
00000010
00001000
01000000
00000100
10000000
00100000
00000001
true ? >
yes
| ?- > test_ex7(100).
...
(460 ms) yes
```
Sign in with Wallet
Connect another wallet