*

Le jeu de la vie de Conway est un automate cellulaire bien connu. Les règles du jeu de la vie sont les suivantes: on dispose d’une grille à deux dimensions dont les cases, appelées cellules, sont soit mortes soit vivantes. À chaque itération, la grille est mise à jour de la façon suivante, en regardant l’état des 8 cellules du voisinage de chaque cellule de la grille:

• Une cellule morte possédant exactement trois cellules voisines vivantes devient vivante
• Une cellule vivante ne possédant pas exactement deux ou trois cellules vivantes meurt

L’objectif de ce petit billet de blog, est d’encoder ces règles en programmation par ensemble de réponses.

Un peu de contexte

Avec le changement climatique, les plantes profittent des douceurs de début de printemps, les fleurs sont plus précoces, les populations d’insectes sont plus précoces; et certaines espèces d’oiseaux ont semble t’il déjà commencé à modifier leur habitudes migratoires et arrivent plus tôt sous nos latitudes. <citation needed>

Nous allons tenter dans ce billet de blog, d’explorer les données d’observation de l’avifaune de Faune-France pour tenter d’en extraire des tendances pour quelques espèces communes.

Le jeu des tentes est un casse-tête logique qui se joue sur une grille rectangulaire ou carrée. Chaque case de la grille peut être occupée par un arbre, une tente ou rester vide. <Nourry (2024)>

Les règles sont les suivantes:

• Il y a des arbres sur certaines cellules de la grille.
• Les tentes sont placées sur des emplacement vides.
• Chaque tente est attaché à un arbre placé sur une case adjacente (pas en diagonale).
• Un arbre ne peut être associé qu’à une seule tente.
• Deux tentes ne peuvent se toucher, même en diagonale.
• Le nombre de tentes de chaque colonne et de chaque ligne est indiqué.
• Certaines cases sont inaccessibles, il est impossible d’y placer une tente. <“Fiche: Jeux de Réflexion - Tentes” (n.d.);Nourry (2024)>

Dans son rapport, Célian Nourry a proposé un programme de résolution de ce problème avec du backtracking implémenté en C. Dans le présent article, on va s’intéresser à un encodage de ce problème avec l’Answer Set Programming.

Un carré latin est un tableau dans lequel chaque ligne et chaque colonne contient le même ensemble de symboles. L’objectif de ce billet est de proposer un ensemble de règles Answer Set Programming pour générer les carrés latins en utilisant la programmation par contrainte.

Les règles du carré latin

alphabet(a;b;c;d;e;f;g;h;i;j;k;l;m;n;o;p;q;r;s;t;u;v;w;x;y;z).

% Chaque cellule a un symbole issu de l'alphabet.
1 { cell(R, C, S): alphabet(S) } 1 :- R = 1..side , C = 1..side.

% Une cellule ne peut contenir qu'une seule valeur
S1 = S2 :- cell(R, C, S1) , cell(R, C, S2).

% Une ligne ne peut contenir plusieurs fois la même valeur
S1 != S2 :- cell(R, C1, S1) , cell(R, C2, S2) , C1 != C2.
% Idem pour les colonnes.
S1 != S2 :- cell(R1, C, S1) , cell(R2, C, S2) , R1 != R2.

% On vérifie que chaque ensemble de symboles
% pour chaque ligne et chaque colonne est le même que la référence
symbol(S) :- cell(1, C, S) , C = 1..side.

:- - symbol(S) , cell(_, _, S).
:- symbol(S) , - cell(R, _, S) , R = 1..side.
:- symbol(S) , - cell(_, C, S) , C = 1..side.

Application avec trois exemples

Les exemples qui suivent sont issus des « Selected Papers on Fun and Games » de Donald E. Knuth, chapitre 36 Quadrata Obscura. Je me suis permis d’ajouter les cellules de la ligne du bas dans l’entrée des problèmes, correspondants aux mots anglais choisis par Knuth; ce qui a pour effet de limiter à un seul le nombre de carrés latins générés par Clingo pour chaque entrées, grâce aux choix judicieux des cellules indiquées dans l’entrée du problème. Une autre approche aurait pu être d’ajouter une contrainte sur les cellules de la ligne du bas pour qu’elle corresponde à un mot d’une liste donnée…

Source: chapitre 33 de « Selected Papers on Fun and Games » de Donald E. Knuth.

Une échelle de mots est un jeu qui consiste à trouver, connaissant un mot de départ et un mot d’arrivée une succession de mots tel que le mot \(i+1\) est semblable au mot \(i\) (au sens où une transformation simple suffit à passer du mot \(i\) au mot \(i+1\)).

Nous allons considerer une version simplifiée du jeu qui n’autorise que l’opération de changement d’une lettre sur les mots (on ignore les opérations « ajout / retrait de lettre » et « changement de l’ordre des lettre »).