Intelligence artificielle et programmation par contraintes

Ces deux sujets sont intimement liés étant donné que la manière de décrire des algorithmes ressemblent beaucoup à du langage naturel. Normalement, en programmation procédurale, il faut tout décrire les étapes à franchir pour obtenir une réponse. Par exemple, si nous voulons savoir si un objet fait parti d’une liste, il faut décrire comment traverser la liste et faire la comparaison. En programmation par contraintes, le logiciel va fouiller tout ce qu’il peut pour trouver une réponse positive et dans le cas contraire, il dira que c’est impossible.

Ici, je vais faire un exemple de ce qu’il est possible de faire et vous allez voir que mis à part la syntaxe qui rebute au début, la logique est très semblable aux définitions directes du problème à résoudre et non à une manière particulière de résoudre le problème.

Dans le jeux Professor Layton and the Curious Village, le puzzle 95 est de résoudre un carré magique. En gros, la somme de toutes les lignes, toutes les colonnes et toutes les diagonales doivent être la même valeur. Ce carré est de 3×3 cases et chaque case à un chiffre différent de 1 à 9.

Voici à quoi ressemble le carré. Le premier est le cas général et le second est le problème tel qu’énoncé avec deux valeurs de fixées pour ne pas avoir plus d’une solution (la rotation du carré amène d’autres réponses).

A B C
D E F
G H I
2 B C
D E F
G 1 I

Pour commencer, nous avons les trois points suivants:

  1. Chaque case est un chiffre de 1 à 9
  2. Chaque case a une valeur unique
  3. La somme des lignes, des colonnes et des diagonales est identique

1. Chaque case est un chiffre de 1 à 9

Ce sont les valeurs primaires avec lesquelles il faut jouer. Nous allons donc définir une « fonction » qui possède chacune.

digit(1).
digit(2).
digit(3).
digit(4).
digit(5).
digit(6).
digit(7).
digit(8).
digit(9).

Ainsi, lorsque nous allons appeler « digit(4). » ou « digit(54). », le logiciel pourra nous dire que la première est vrai et la seconde est fausse. De plus, si nous choisissons la variable X et demandons les valeurs qu’elle peut prendre si X est un digit « digit(X). », il nous retournera toutes les valeurs de 1 à 9.

2. Chaque case a une valeur unique

C’est ici que la syntaxe devient bizarre. Les listes d’objets sont déclarées entre crochets et séparées par des virgules. Pour sortir des valeurs d’une liste, nous pouvons prendre la première valeur et la séparer du reste de la liste. La syntaxe [X|Y] veut dire que X est le premier objet et Y est le restant de la liste. Pour savoir si une valeur quelconque fait partie de la liste, nous écrivons ceci:

memberof(S, [X|Y]) :- S=X ; memberof(S, Y).

Qui signifie:

  • Rouge: L’objet S représente ce que nous espérons trouver dans la liste qui est composé d’un premier objet X et du restant de la liste Y.
  • Bleu: Cette fonction est vrai si tout le restant est vrai.
  • Orange: L’objet S est identique à l’objet X (qui est le premier)
  • Vert: Ce qui est à gauche OU ce qui est à droite. Donc, si S n’est pas égal à X, faire ce qui suit.
  • Violet: Demander si l’objet S se trouve dans le restant de la liste qui est Y. Étant donné que le premier objet est enlevé chaque fois, la liste va être vide un jour et tous les objets vont avoir été comparés à S.

Cette fonction nous dit si un objet fait parti du restant. Alors pour savoir si tous les objets sont différents, il faut prendre chacun des objets d’une liste et vérifier qu’il n’est pas ailleurs dans la liste. Ceci est fait comme suit:

alldiff([_]).alldiff([X|Y]) :-
memberof(X, Y) -> fail; true,
alldiff(Y).
  • Rouge: Étant donné que dans la définition suivante, la portion en orange appelle la fonction « alldiff » avec une liste qui possède un élément de moins chaque fois, le dernier appel sera une liste d’un seul objet. Une liste d’un seul objet est défini comme [X]. La raison pour laquelle le X est remplacé par un souligné, c’est que dans cette définition, nous n’utilisons pas cette variable, alors le souligné représente une variable qui ne nous intéresse pas. Alors en gros, cette ligne veut dire que toute liste d’un seul objet n’a que des objets différents.
  • Vert: Une liste d’objet est définie comme étant toute différente si toutes les lignes bleue et orange sont vraies.
  • Bleu: En cherchant le premier objet de la liste (X) parmi le restant de la liste (Y), s’il y en a un qui est identique, alors le test échoue (fail). S’il n’en trouve pas, alors la ligne est vrai (true) et la ligne orange est vérifiée.
  • Orange: Pour savoir si le reste de la liste est toute différente.

3. Le puzzle en soit

Le test pour les sommes sont incorporées dans la fonction puzzle que je vais définir à l’instant:

puzzle(A,B,C,D,E,F,G,H,I) :-
digit(A),digit(B),digit(C),digit(D),digit(E),digit(F),digit(G),digit(H),digit(I),
alldiff([A,B,C,D,E,F,G,H,I]),
M is A+B+C,
N is D+E+F, M=N,
N is G+H+I, M=N,
N is A+D+G, M=N,
N is B+E+H, M=N,
N is C+F+I, M=N,
 

N is A+E+I, M=N,
N is C+E+G, M=N.

Puisque nous voulons pouvoir résoudre tous les carrés magiques et même en spécifier des particuliers, toutes les cases sont dans la définition en noir.

  • Rouge: Chacun des nombres sont des digit
  • Vert: La vérification que la liste formée de tous les paramètres sont différents les uns des autres
  • Bleu: Les sommes des 3 lignes, 3 colonnes et 2 diagonales sont identiques.

L’exécution

Maintenant, nous avons besoin d’un logiciel qui comprend le tout. Un très connu est SWI-Prolog et s’installe bien dans Windows. Vous pouvez prendre la source complète du programme qui suit, l’enregistrer dans un fichier avec l’extension « .pl » et l’exécuter en double-cliquant dessus une fois SWI-Prolog installé.

/* puzzle(2,B,C,D,E,F,G,1,I). */ 

digit(1).
digit(2).
digit(3).
digit(4).
digit(5).
digit(6).
digit(7).
digit(8).
digit(9).

memberof(S, [X|Y]) :- S=X ; memberof(S, Y).

alldiff([_]).

alldiff([X|Y]) :-
memberof(X, Y) -> fail; true,
alldiff(Y).

puzzle(A,B,C,D,E,F,G,H,I) :-
digit(A),digit(B),digit(C),digit(D),digit(E),digit(F),digit(G),digit(H),digit(I),
alldiff([A,B,C,D,E,F,G,H,I]),
M is A+B+C,
N is D+E+F, M=N,
N is G+H+I, M=N,

N is A+D+G, M=N,
N is B+E+H, M=N,
N is C+F+I, M=N,

N is A+E+I, M=N,
N is C+E+G, M=N.

Une fois ouvert, vous pouvez demander puzzle(A,B,C,D,E,F,G,H,I). pour demander toutes les possibilités ou puzzle(2,B,C,D,E,F,G,1,I). pour la solution particulière. Cette dernière affiche après 10 secondes:

B = 9,
C = 4,
D = 7,
E = 5,
F = 3,
G = 6,
I = 8

Ce qui représente le carré magique avec la somme à 15 comme suit:

2 9 4
7 5 3
6 1 8