Le blog d'un Geekus biologicus juvénile

Jeu des tentes en Answer Set Programming

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:

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.

Implémentation des règles du jeu en ASP

Començons par définir quelques contraintes sur la grille de jeu:

% Les dimensions de la grille:
#const width=6.
#const height=6.

% les symboles emoji que nous allons utiliser:
#const tent="⛺".
#const tree="🌳".
#const herb="🌿".

% Une cellule de la grille, à la ligne R et la colonne C, représentée par le predicat cell(R, C, V), contient la valeur V.

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

% On s'assure de ne pas dépasser de la grille (on choisit de commencer le compte des cellules à 1.)
R > 0 , R <= width , C > 0 , R <= height :- cell(R, C, _).

% Chaque case vide de la grille peut être soit une tente, soit rester vide.
position(R, C) :- R = 1..width , C = 1..height.
occupied(R, C) :- cell(R, C, herb) , position(R, C).
occupied(R, C) :- cell(R, C, tree) , position(R, C).
empty(R, C) :- not occupied(R, C) , position(R, C).

symbol(tent;"").
1 { cell(R, C, V) : symbol(V) } 1 :- empty(R, C).

cell(1, 1, tree).

Comment encoder le voisinage d’une cellule ?

Une approche pourrait être d’utiliser une règle ASP pour chacun des 4 voisins de von Neumann:

neighbor(R + 1, C) :- cell(R, C).
neighbor(R - 1, C) :- cell(R, C).
neighbor(R, C + 1) :- cell(R, C).
neighbor(R, C - 1) :- cell(R, C).

cell(1, 1).

clingo version 5.8.0
Reading from /tmp/babel-xyJUQj/clingo-DP7Qhl
Solving...
Answer: 1 (Time: 0.000s)
cell(1,1) neighbor(1,0) neighbor(1,2) neighbor(0,1) neighbor(2,1)
SATISFIABLE

Models       : 1
Calls        : 1
Time         : 0.000s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s

Cela a pour inconvénient que tous les atomes neighbor/2 sont considérés dans l’ensemble de réponse. Or dans notre cas on veut choisir une cellule voisine l’arbre pour y mettre une tente. Il nous faut donc un moyen de faire ce choix. On peut écrire ce choix de la façon suivante:

% On commence par déterminer les différents delta de position d'un voisinage de von Neumann
neumann((-1, 0); (0, -1); (1, 0); (0, 1)).

% Puis on en choisit 1.
1 = { neighbor(R + R_delta, C + C_delta) : neumann((R_delta, C_delta)) } :- cell(R, C).

cell(1, 1).

#show neighbor/2.

clingo version 5.8.0
Reading from /tmp/babel-xyJUQj/clingo-nTSrsX
Solving...
Answer: 1 (Time: 0.000s)
neighbor(1,0)
Answer: 2 (Time: 0.000s)
neighbor(2,1)
Answer: 3 (Time: 0.000s)
neighbor(1,2)
Answer: 4 (Time: 0.000s)
neighbor(0,1)
SATISFIABLE

Models       : 4
Calls        : 1
Time         : 0.000s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s

On peut implémenter la règle d’adjacence des tentes et des arbres:


% Le voisinage de von Neumann:
neumann((-1, 0); (0, -1); (1, 0); (0, 1)).

% On choisit une cellule du voisinage
1 = { neighbor_tent_tree(R_tent, C_tent, R_tent + R_delta, C_tent + C_delta): neumann((R_delta, C_delta)) } :- cell(R_tent, C_tent, tent).

% On s'assure que cette cellule est bien un arbre
:- neighbor_tent_tree(_, _, R_tree, C_tree) , not cell(R_tree, C_tree, tree).

Un arbre est attaché à une seule tente

% Pour que cette règle soit satisfaite,
% il faut que le prédicat neighbor_tent_tree ne concerne qu'un seul couple arbre - tente
% Pour cela, de la même manière que pour s'assurer qu'une cellule a une unique valeur,
% on s'assure que pour tout arbre, s'il y a un prédicat neighbor_tent_tree, il est unique.
R_cell1 = R_cell2 , C_cell1 = C_cell2 :- neighbor_tent_tree(R_cell1, C_cell1, R_tree, C_tree) , neighbor_tent_tree(R_cell2, C_cell2, R_tree, C_tree).

Deux tentes ne peuvent pas être voisines: ni adjacentes, ni placées en diagonales

Pour cette règle, on peut utiliser le même principe que pour le voisinage des arbres, mais cette fois ci en utilisant le voisinage de Moore.

moore((-1,-1); (-1,0); (-1,1); (0,-1); (0,1); (1,-1); (1,0); (1,1)).

clingo version 5.8.0
Reading from /tmp/babel-xyJUQj/clingo-4f8c25
Solving...
Answer: 1 (Time: 0.001s)
moore((-1,-1)) moore((-1,0)) moore((-1,1)) moore((0,-1)) moore((0,1)) moore((1,-1)) moore((1,0)) moore((1,1))
SATISFIABLE

Models       : 1
Calls        : 1
Time         : 0.001s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.001s


:- moore((R_delta, C_delta))
        , cell(R, C, tent)
        , cell(R + R_delta, C + C_delta, tent).

Contrainte sur le nombre de tentes par colonne ou ligne

% On introduit deux nouveaux prédicats:
% tent_column(C, N). qui indique que N tentes sont placées sur la colonne N,
% et tent_row(R, N). pour les lignes.

% La contrainte qu'on cherche à satisfaire est exprimée avec un compte des tentes sur chaque ligne:
% On commence par compter les tentes de chaque ligne, et chaque colonne
row_count(R, N) :- N = { cell(R, _, tent) } , R = 1..width.
column_count(C, N) :- N = { cell(_, C, tent) } , C = 1..height.

% Puis ajoute une contrainte pour chaque ligne, pour que cela respecte les données du problème.
N1 = N2 :- row_count(R, N1) , tent_row(R, N2).
N1 = N2 :- column_count(C, N1) , tent_column(C, N2).

Toutes les règles ensembles

% Les dimensions de la grille:
#const width=6.
#const height=6.

% les symboles emoji que nous allons utiliser:
#const tent="⛺".
#const tree="🌳".
#const herb="🌿".

% Une cellule de la grille, à la ligne R et la colonne C, représentée par le predicat cell(R, C, V), contient la valeur V.

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

% On s'assure de ne pas dépasser de la grille (on choisit de commencer le compte des cellules à 1.)
R > 0 , R <= width , C > 0 , R <= height :- cell(R, C, _).

% Chaque case vide de la grille peut être soit une tente, soit rester vide.
position(R, C) :- R = 1..width , C = 1..height.
occupied(R, C) :- cell(R, C, herb) , position(R, C).
occupied(R, C) :- cell(R, C, tree) , position(R, C).
empty(R, C) :- not occupied(R, C) , position(R, C).

symbol(tent;"").
1 { cell(R, C, V) : symbol(V) } 1 :- empty(R, C).

cell(1, 1, tree).
% Pour que cette règle soit satisfaite,
% il faut que le prédicat neighbor_tent_tree ne concerne qu'un seul couple arbre - tente
% Pour cela, de la même manière que pour s'assurer qu'une cellule a une unique valeur,
% on s'assure que pour tout arbre, s'il y a un prédicat neighbor_tent_tree, il est unique.
R_cell1 = R_cell2 , C_cell1 = C_cell2 :- neighbor_tent_tree(R_cell1, C_cell1, R_tree, C_tree) , neighbor_tent_tree(R_cell2, C_cell2, R_tree, C_tree).
moore((-1,-1); (-1,0); (-1,1); (0,-1); (0,1); (1,-1); (1,0); (1,1)).
:- moore((R_delta, C_delta))
        , cell(R, C, tent)
        , cell(R + R_delta, C + C_delta, tent).

% On introduit deux nouveaux prédicats:
% tent_column(C, N). qui indique que N tentes sont placées sur la colonne N,
% et tent_row(R, N). pour les lignes.

% La contrainte qu'on cherche à satisfaire est exprimée avec un compte des tentes sur chaque ligne:
% On commence par compter les tentes de chaque ligne, et chaque colonne
row_count(R, N) :- N = { cell(R, _, tent) } , R = 1..width.
column_count(C, N) :- N = { cell(_, C, tent) } , C = 1..height.

% Puis ajoute une contrainte pour chaque ligne, pour que cela respecte les données du problème.
N1 = N2 :- row_count(R, N1) , tent_row(R, N2).
N1 = N2 :- column_count(C, N1) , tent_column(C, N2).

Un exemple


% Entrées du problème
% Position des arbres
cell(R, C, tree) :- tree(R, C).
tree(1, 4).
tree(2, 2).
tree(2, 6).
tree(3, 3).
tree(3, 5).
tree(4, 4).
tree(5, 2).
tree(6, 5).

% Colonnes
tent_column(1, 1).
tent_column(2, 2).
tent_column(3, 0).
tent_column(4, 2).
tent_column(5, 1).
tent_column(6, 2).

% Lignes
tent_row(1, 2).
tent_row(2, 0).
tent_row(3, 3).
tent_row(4, 0).
tent_row(5, 2).
tent_row(6, 1).

clingo version 5.8.0
Reading from /tmp/babel-xyJUQj/clingo-rlTcpd
Solving...
Answer: 1 (Time: 0.005s)
cell(1,1,"🌳") cell(1,4,"🌳") cell(2,2,"🌳") cell(2,6,"🌳") cell(3,3,"🌳") cell(3,5,"🌳") cell(4,4,"🌳") cell(5,2,"🌳") cell(6,5,"🌳") position(1,1) position(1,2) position(1,3) position(1,4) position(1,5) position(1,6) position(2,1) position(2,2) position(2,3) position(2,4) position(2,5) position(2,6) position(3,1) position(3,2) position(3,3) position(3,4) position(3,5) position(3,6) position(4,1) position(4,2) position(4,3) position(4,4) position(4,5) position(4,6) position(5,1) position(5,2) position(5,3) position(5,4) position(5,5) position(5,6) position(6,1) position(6,2) position(6,3) position(6,4) position(6,5) position(6,6) occupied(1,1) occupied(1,4) occupied(2,2) occupied(2,6) occupied(3,3) occupied(3,5) occupied(4,4) occupied(5,2) occupied(6,5) symbol("⛺") symbol("") moore((-1,-1)) moore((-1,0)) moore((-1,1)) moore((0,-1)) moore((0,1)) moore((1,-1)) moore((1,0)) moore((1,1)) tent_row(1,2) tent_row(2,0) tent_row(3,3) tent_row(4,0) tent_row(5,2) tent_row(6,1) tent_column(1,1) tent_column(2,2) tent_column(3,0) tent_column(4,2) tent_column(5,1) tent_column(6,2) tree(1,4) tree(2,2) tree(2,6) tree(3,3) tree(3,5) tree(4,4) tree(5,2) tree(6,5) empty(1,2) empty(1,3) empty(1,5) empty(1,6) empty(2,1) empty(2,3) empty(2,4) empty(2,5) empty(3,1) empty(3,2) empty(3,4) empty(3,6) empty(4,1) empty(4,2) empty(4,3) empty(4,5) empty(4,6) empty(5,1) empty(5,3) empty(5,4) empty(5,5) empty(5,6) empty(6,1) empty(6,2) empty(6,3) empty(6,4) empty(6,6) cell(1,2,"⛺") cell(1,3,"") cell(1,5,"⛺") cell(1,6,"") cell(2,1,"") cell(2,3,"") cell(2,4,"") cell(2,5,"") cell(3,1,"") cell(3,2,"⛺") cell(3,4,"⛺") cell(3,6,"⛺") cell(4,1,"") cell(4,2,"") cell(4,3,"") cell(4,5,"") cell(4,6,"") cell(5,1,"⛺") cell(5,3,"") cell(5,4,"") cell(5,5,"") cell(5,6,"⛺") cell(6,1,"") cell(6,2,"") cell(6,3,"") cell(6,4,"⛺") cell(6,6,"") column_count(1,1) column_count(2,2) column_count(3,0) column_count(4,2) column_count(5,1) column_count(6,2) row_count(1,2) row_count(2,0) row_count(3,3) row_count(4,0) row_count(5,2) row_count(6,1)
SATISFIABLE

Models       : 1+
Calls        : 1
Time         : 0.005s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.005s
1 2 0 2 1 2
2 🌳 ⛺ 🌳 ⛺
0 🌳 🌳
3 ⛺ 🌳 ⛺ 🌳 ⛺
0 🌳
2 ⛺ 🌳 ⛺
1 ⛺ 🌳

References

“Fiche: Jeux de Réflexion - Tentes.” n.d. éducmat. Accessed December 11, 2025. https://www.educmat.fr/categories/jeux_reflexion/fiches_jeux/camping/index.php.

Nourry, Célian. 2024. “Rapport de Projet de R´esolution du jeu de Tentes.” Rapport de projet. Université Paris 8. https://code.up8.edu/cnourry/jeu-de-tentes.