Tent Game in Answer Set Programming

December 29, 2025

fr: Jeu des tentes en Answer Set Programming

The Tent game is a logic puzzle on a square or rectangular grid. Each grid cell can have a tree, a tent or stay empty. <Nourry (2024)>

The following rules must be respected:

Tent can be placed on empty cells.

Each tent is attached to a tree placed on an adjacent cell.

A tree cannot be attached to more than one tent.

Two tents cannot be placed on adjacent, nor diagonal cells.

The number of tents on each row and column is specified.

Some cells are not accessible, no tent can be pitched there. <“Fiche: Jeux de Réflexion - Tentes” (n.d.);Nourry (2024)>

The aim of this article is to propose a implementation of the Tent game in Answer Set Programming.

Tent game in Answer Set Programming

Let’s begin with some constraint on the game grid.

% The size of the grid:
#const width=6.
#const height=6.

% Some emoji
#const tent="⛺".
#const tree="🌳".
#const herb="🌿".

% A cell on the grid at row R and column C is represented by the predicate cell(R, C, V) and contain the value V.

% A cell cannot contain more than one value
V1 = V2 :- cell(R, C, V1), cell(R, C, V2).

% We check the border of the grid. We start indicing by 1.
R > 0 , R <= width , C > 0 , R <= height :- cell(R, C, _).

% Each empty cell can remain empty, or accept a tent
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).

How to encode the tent neighborhood constraint?

An approach could be to use an ASP rule for each of the four von Neumann neighbors.

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-MfTgfu/clingo-KAEfOE
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

However, this way, each atom neighbor/2 are considered true in the answer set, though in our case, we muse choose a tree neighbor cell to put a tent on it. We have to make a choice. In ASP, we can write it as:

% We first define all position delta for von Neumann neighborhood
neumann((-1, 0); (0, -1); (1, 0); (0, 1)).

% Then, we chose one neighbor
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-MfTgfu/clingo-UY6vfe
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

We can now implement the adjacency rule for the tents and the trees:


% von Neumann neighborhood
neumann((-1, 0); (0, -1); (1, 0); (0, 1)).

% A neighboring cell of a tent
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).

% We check it is indeed a tree
:- neighbor_tent_tree(_, _, R_tree, C_tree) , not cell(R_tree, C_tree, tree).

A tree is attached to a single tent

% Similar to the rule checking the uniqueness of the cell value,
% We check the uniqueness of the tree neighbor tent, if any.
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).

Two tent cannot be located one next to the other

We can use the same principle as before, this time using the Moore neighborhood.

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-MfTgfu/clingo-7ekHqS
Solving...
Answer: 1 (Time: 0.000s)
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.000s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s

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

Constraint on the number of tent per row and column

% We introduce two new predicates:
% tent_column(C, N). that counts the number of tent in column C.
% and tent_row(R, N). for rows.

% We begin by counting the number of tent per row and column
row_count(R, N) :- N = { cell(R, _, tent) } , R = 1..width.
column_count(C, N) :- N = { cell(_, C, tent) } , C = 1..height.

% Then we ensure the count respect the input
N1 = N2 :- row_count(R, N1) , tent_row(R, N2).
N1 = N2 :- column_count(C, N1) , tent_column(C, N2).

All rules together

% The size of the grid:
#const width=6.
#const height=6.

% Some emoji
#const tent="⛺".
#const tree="🌳".
#const herb="🌿".

% A cell on the grid at row R and column C is represented by the predicate cell(R, C, V) and contain the value V.

% A cell cannot contain more than one value
V1 = V2 :- cell(R, C, V1), cell(R, C, V2).

% We check the border of the grid. We start indicing by 1.
R > 0 , R <= width , C > 0 , R <= height :- cell(R, C, _).

% Each empty cell can remain empty, or accept a tent
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).

% Similar to the rule checking the uniqueness of the cell value,
% We check the uniqueness of the tree neighbor tent, if any.
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).

% We introduce two new predicates:
% tent_column(C, N). that counts the number of tent in column C.
% and tent_row(R, N). for rows.

% We begin by counting the number of tent per row and column
row_count(R, N) :- N = { cell(R, _, tent) } , R = 1..width.
column_count(C, N) :- N = { cell(_, C, tent) } , C = 1..height.

% Then we ensure the count respect the input
N1 = N2 :- row_count(R, N1) , tent_row(R, N2).
N1 = N2 :- column_count(C, N1) , tent_column(C, N2).

An example


% Problem input

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).

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

% Rows
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-MfTgfu/clingo-6fCwzE
Solving...
Answer: 1 (Time: 0.003s)
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,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,1) 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,1,"") 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.003s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.003s

	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.