Laboratoire 9

Sommaire

Nombres triangulaires

Un nombre triangulaire peut se calculer avec la formule suivante :

\(T(n) = \dfrac{n(n+1)}{2}\)

Écrire une relation triangular(N, T) en utilisant is pour l’évaluation mathématique.

Essayer les deux requêtes suivantes :

?- triangular(3, T).
?- triangular(N, 3).

Quel est le problème ?

Redéfinir cette relation en utilisant les contraintes de la bibliothèque clpfd et réessayer.

Knights and Knaves

Sur une île étrange, vous rencontrez trois habitants : A, B, et C. Les chevaliers disent toujours la vérité. Les fourbes mentent systématiquement.

  • L’habitant A énonce « Nous sommes tous des fourbes ».
  • L’habitant B énonce « Exactement l’un d’entre nous est un chevalier »
  • L’habitant C ne dit rien.

Trouver qui parmi, A, B, et C est chevalier, et qui est fourbe.

Quelle réponse est correcte ?

On vous pose la question suivante :

Parmi les réponses suivantes, laquelle est correcte ?
A. Toutes les réponses après celle-ci
B. Aucune des réponses après celle-ci
C. Toutes les réponses avant celle-ci
D. Au moins une des réponses avant celle-ci
E. Aucune des réponses avant celle-ci
F. Aucune des réponses avant celle-ci

Modéliser cela sous forme de formules de logique propositionnelle, et résoudre le problème avec clpb.

Coloration de graphe binaire

Soit un graphe avec trois nœuds : A, B, et C. A est connecté à B, et B est connecté à C, ce qu’on peut donc représenter comme suit :

A -- B -- C

On souhaite colorier le graphe avec deux couleurs : on souhaite donc assigner une couleur à chaque nœud. Une contrainte importante lors de la coloration de graphe est que deux nœuds adjacent (qui partagent une arrête) ne peuvent pas avoir la même couleur.

Modéliser ce problème en utilisant la bibliothèque clpb, et énumérer toutes les solutions. On s’attend à avoir deux solutions.

Indices :

  • la couleur d’un nœud peut être représentée par un booléen
  • les contraintes peuvent être représentées par une formule logique

Coloration de graphe

On souhaite refaire une coloration de graphe, cette fois-ci avec le graphe suivant :

A -
|  `C - D
B -´

En version textuelle, on les arrêtes suivantes : (A, B), (A, C), (B, C), (C, D).

Il faudra ici utiliser 3 couleurs, qu’on représentera donc par des nombres.

Modéliser ce problème en utilisant la bibliothèque clpfd, et énumérer toutes les solutions. On s’attend à avoir 12 solutions.

Problème des 8 dames

Renseignez vous sur le problème des 8 dames. Regardez ensuite comment il est modélisé en Prolog avec clpfd : ici.

Expliquez comment le code fonctionne.

Carré magique

Un carré magique d’ordre n est un tableau d’entiers de taille n×n, où, pour une constante magique m :

  • la somme de chaque ligne est égale à m
  • la somme de chaque colonne est égale à m
  • la somme chaque diagonale est égale à m
  • toutes les cases du carré contiennent un nombre différent

Par exemple, le carré suivant est magique avec m = 15

Définir une relation magic_square(N, M, Square) qui permet de calculer des carrés magiques.

Quelques éléments utiles :

  • append/2 permet d’aplatir une liste de liste, par exemple, append([[1,2],[3,4]], [1,2,3,4])).
  • transpose/2 permet de transposer un tableau, c’est-à-dire transformer les lignes en colonnes et inversement
  • sum/3 permet de faire une contrainte sur la somme d’une liste, par exemple, sum([1,2,3], #=, N).
  • maplist est utile pour appliquer une relation à chaque élément d’une liste, par exemple :
    • maplist(between(0,1), L) restreint tous les éléments de la liste L à être entre 0 et 1, car between(0,1,N) restreint N à être entre 0 et 1.
    • maplist(plus(3), [1, X], [Y, 2]) trouve les valeurs de X et Y telles que 3+1=Y et 3+X=2 (plus/3 est le prédicat d’addition). Cela revient à faire plus(3,1,Y), plus(3,Y,2).

Pour définir la relations, il est recommandé de procéder itérativement :

  • d’abord vérifier que la somme de chaque ligne est égale à M
  • ensuite vérifier que la somme de chaque colonne est égale à M
  • ensuite extraire les diagonales et vérifier que leur somme est égale à M

Générez finalement une solution pour magic_square(3, 15, S) et validez à la main qu’elle est correcte.