Quelques problèmes en Answer Set Programming

9 novembre 2025

Cette page rassemble quelques solutions en Answer Set Programming (avec clingo) à une sélection de problèmes de logique originaires de sources diverses et variées.

Le grand pique-nique

When they started off on the great annual picnic every wagon in town was pressed into service, each one carrying the same number of people.

Half way to the picnic ground ten wagons broke down, so it was necessary for each of the remaining wagons to carry one more person.

When they started for home it was discovered that fifteen more wagons were out of commission, so on the return trip there were three persons more in each wagon than when they started out in the morning.

Now who can tell how many people attended the great annual picnic?

Brilliant Order logic

Source: https://brilliant.org

Qu°1

4 is before 1 and 2.

3 is after 1 and 2.

2 is before 1.

#const n=4.

values(1..n).
before(4, (1;2)).
after(3, (1;2)).
before(2, 1).


values(1..n).

after(After, Before) :- before(Before, After).
before(Before, After) :- after(After, Before).

n { position(Value, Position): values(Value), values(Position) } n.

:- position(Value, Position1), position(Value, Position2) , Position1 != Position2.
:- position(Value1, Position), position(Value2, Position) , Value1 != Value2.


Position1 < Position2 :- before(Value1, Value2) , position(Value1, Position1), position(Value2, Position2).

#show position/2.

4,2,1,3

Qu°2

- 1 is after 4 and before 2.
- 2 and 4 are after 3.

The same inference rules can be used, only the input data changes.


#const n=4.


values(1..n).

after(After, Before) :- before(Before, After).
before(Before, After) :- after(After, Before).

n { position(Value, Position): values(Value), values(Position) } n.

:- position(Value, Position1), position(Value, Position2) , Position1 != Position2.
:- position(Value1, Position), position(Value2, Position) , Value1 != Value2.


Position1 < Position2 :- before(Value1, Value2) , position(Value1, Position1), position(Value2, Position2).

#show position/2.

after(1, 4).
before(1, 2).
after((2; 4), 3).

3,4,1,2

Qu°3

4 is before 1 and 2

3 is after 1 and 2

2 is before 1

#const n=4.

values(1..n).

after(After, Before) :- before(Before, After).
before(Before, After) :- after(After, Before).

n { position(Value, Position): values(Value), values(Position) } n.

:- position(Value, Position1), position(Value, Position2) , Position1 != Position2.
:- position(Value1, Position), position(Value2, Position) , Value1 != Value2.


Position1 < Position2 :- before(Value1, Value2) , position(Value1, Position1), position(Value2, Position2).

#show position/2.

before(4, (1;2)).
after(3, (1;2)).
before(2, 1).

4,2,1,3

Qu°4

1 is after 4 and before 2.

2 and 4 are after 3.

#const n=4.


values(1..n).

after(After, Before) :- before(Before, After).
before(Before, After) :- after(After, Before).

n { position(Value, Position): values(Value), values(Position) } n.

:- position(Value, Position1), position(Value, Position2) , Position1 != Position2.
:- position(Value1, Position), position(Value2, Position) , Value1 != Value2.


Position1 < Position2 :- before(Value1, Value2) , position(Value1, Position1), position(Value2, Position2).

#show position/2.

after(1, 4).
before(1, 2).
after((2;4), 3).

3,4,1,2

Qu°5

4 is before 3 and 2.

1 is after 3.

2 is after 1.

#const n=4.


values(1..n).

after(After, Before) :- before(Before, After).
before(Before, After) :- after(After, Before).

n { position(Value, Position): values(Value), values(Position) } n.

:- position(Value, Position1), position(Value, Position2) , Position1 != Position2.
:- position(Value1, Position), position(Value2, Position) , Value1 != Value2.


Position1 < Position2 :- before(Value1, Value2) , position(Value1, Position1), position(Value2, Position2).

#show position/2.

before(4, (3;2)).
after(1, 3).
after(2, 1).

4,3,1,2

Relative comparisons

The robots are comparing ages to line up correctly.

Put the robots in the correct order using clues about their ages.

The robot in 4th is older than the robot in 1st.

The robot is 4th is younger than in neighbor.

The robot in 2nd is youngest.

The robots have to chose their slots, according to their age, and the slots are:

365

500

700

999

#const n=4.

slot(1..n).
robot(365;500;701;999).

% Each slot is associated with a single robot
n { position(Robot, Slot): slot(Slot), robot(Robot) } n.

% Two robots set at the same slot must be the same robot
Robot1 = Robot2 :- position(Robot1, Slot) , position(Robot2, Slot).

% Older means the age is higher
OldRobot > YoungRobot :- older(OldRobot, YoungRobot).
younger(YoungRobot, OldRobot) :- older(OldRobot, YoungRobot).
older(OldRobot, YoungRobot) :- younger(YoungRobot, OldRobot).

% The robot in 4th slot is older than the robot in 1st
older(Robot4, Robot1) :- position(Robot4, 4) , position(Robot1, 1).

% The robot in 4th slot is younger than its neighbor (i.e, the robots in 3th).
younger(Robot4, Robot3) :- position(Robot4, 4) , position(Robot3, 3).

% The robot in 2nd slot is the youngest
OtherAge > Robot2Age :- position(Robot2Age, 2) , position(OtherAge, OtherPosition), OtherPosition != 2.

#show position/2.

500,365,999,701

Dans le mille

Dans quel(s) cercle(s) concentrique(s) de cette cible inhabituelle, et combien de fois devrait-on tirer au minimum pour atteindre le chiffre 100 ? (NO_ITEM_DATA:odellProblemesPourSuper1981)

#const objectif=100. % On cherche à atteindre ce chiffre.

% Les valeurs de chaque cercle concentriques de la cible
cercle(11;13;31;33;42;44;46).

% On choisit le nombre de fois où on tire une flèchette sur le cercle C
{ flechettes(Cercle, Count) : cercle(Cercle), Count = 0..10 }.
% On s'assure que chaque cercle est compté une seule fois
Count1 = Count2 :- flechettes(Cercle, Count1), flechettes(Cercle, Count2).

% On compte le score fait sur chaque cercle
cercle_score(Cercle, Count * Cercle) :- cercle(Cercle) , flechettes(Cercle, Count).

% On fait la somme pour le score total
score(Total) :- #sum { Score : cercle_score(_, Score) } = Total.

% On s'assure que le total fait bien le chiffre visé
:- score(Total) , objectif != Total.

% On compte le nombre de flèchettes utilisées
tirs(N) :- #sum { Count: flechettes(_, Count) } = N.

% On minimize le nombre de flèchettes utilisées
#minimize { N: tirs(N) }.

#show tirs/1.
#show score/1.
#show flechettes/2.

clingo version 5.8.0
Reading from /tmp/babel-TPw3fw/clingo-ulx9zx
Solving...
Answer: 1 (Time: 4.983s)
flechettes(11,2) flechettes(13,6) tirs(8) score(100)
Optimization: 8
OPTIMUM FOUND

Models       : 1
  Optimum    : yes
Optimization : 8
Calls        : 1
Time         : 7.772s (Solving: 2.81s 1st Model: 0.03s Unsat: 2.79s)
CPU Time     : 7.771s

References

Odell & Charette (1981) Problèmes Pour Super - Cracks.