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 valeurS1=S2:-cell(R,C,S1),cell(R,C,S2).% Une ligne ne peut contenir plusieurs fois la même valeurS1!=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érencesymbol(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…
L’exemple 5 ✕ 5
p
x
i
m
p
m
p
% L'entrée du problème (a)#constside=5.cell(1,1,p).cell(2,4,x).cell(3,3,i).cell(4,2,m).cell(4,4,p).cell(5,1,m).cell(5,5,p).% wordcell(5,1,m).cell(5,2,i).cell(5,3,x).cell(5,4,u).cell(5,5,p).#showcell/3.
p
u
m
i
x
i
z
p
x
m
x
p
i
m
u
u
m
a
p
i
m
i
x
u
p
L’exemple 6 ✕ 6
x
i
p
x
m
p
i
m
i
x
x
i
% L'entrée du problème (b)#constside=6.cell(1,4,x).cell(2,3,i).cell(2,4,p).cell(2,5,x).cell(3,2,m).cell(3,3,p).cell(3,4,i).cell(4,1,m).cell(4,2,i).cell(4,3,x).cell(5,2,x).cell(5,6,i).% wordcell(6,1,p).cell(6,2,r).cell(6,3,e).cell(6,4,m).cell(6,5,i).cell(6,6,x).#showcell/3.
i
e
r
x
m
p
r
c
i
p
x
m
x
m
p
i
e
r
m
i
x
h
r
e
e
x
m
r
p
i
p
r
e
m
i
x
Exemple 7 ✕ 7
i
x
m
m
p
x
m
p
i
i
x
e
x
p
% L'entrée du problème (d)#constside=7.cell(1,1,i).cell(1,2,x).cell(1,7,m).cell(2,2,p).cell(2,3,x).cell(3,2,m).cell(3,3,p).cell(3,4,i).cell(4,3,i).cell(4,5,x).cell(4,7,e).cell(5,4,x).cell(6,1,p).% wordcell(7,1,s).cell(7,2,i).cell(7,3,m).cell(7,4,p).cell(7,5,l).cell(7,6,e).cell(7,7,x).#showcell/3.