---
# System prepended metadata

title: TP Prolog - s11 - ISC IL 3a
tags: [prolog]

---

###### 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).

![](https://nextcloud.simonbraillard.ch/s/MrkgpzKKoXGXyMQ/preview)

## 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
![](https://nextcloud.simonbraillard.ch/s/NzNjc7gCS7gpyyA/preview)
### Version naïve 2
![](https://nextcloud.simonbraillard.ch/s/b3wFc3jRZyCYXxr/preview)
### Version affinée
![](https://nextcloud.simonbraillard.ch/s/SYrHEzyWgNe9ce6/preview)
### Version triplets primitifs
![](https://nextcloud.simonbraillard.ch/s/FjwQrftbnr3Ws6Y/preview)
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
```