Examples

In this section we show how to use ASPECT syntax in various problems typical of the ASP context.

Note

More examples are available in the GitHub repository.

Graph Coloring

Graph coloring is a well-known problem that is often used as an example to introduce answer set programming to students. The problem consists of assigning colors to vertices of a graph such that two adjacent vertices do not share the same color.

The ASP encoding of the problem consists of node(N) atoms to denote the nodes of the graph where N is an index that identifies the node. Also part of the encoding are arc(A,B) atoms indicating the edges of the graph and color(N,Color) atoms indicating the colour associated with each vertex.

node(0..5).

col(yellow). col(orange). col(green). col(cyan).

edge(0, 1). edge(0, 3). edge(0, 2). edge(0, 4). edge(0, 5).
edge(1, 3). edge(1, 4).
edge(2, 3).
edge(3, 4). edge(3, 5).

1 {color(X, C): col(C)} 1 :- node(X).
:- edge(X, Y), col(C), color(X, C), color(Y, C).

In this problem the coordinates of the various nodes in the graph are not important so it is easier to visualize the solutions using the graph atoms. The ASPECT code required for the visualization is given below.

aspect_graphcolornode(X,Color,circle) :- color(X,Color).
aspect_graphdrawline(A,B) :- edge(A,B).

Tip

To try this example (using clingo as ASP solver) run the following command:

clingo ./examples/01-graph-coloring/graph.lp | java -jar ASPECT.jar

If you want to draw 5 solutions use:

clingo ./examples/01-graph-coloring/graph.lp 5 | java -jar ASPECT.jar

If you want the 5 solutions drawn in a single beamer presentation try:

clingo ./examples/01-graph-coloring/graph.lp 5 | java -jar ASPECT.jar --beamer

the result in this last case is better by also setting the resize parameter

clingo ./examples/01-graph-coloring/graph.lp 5 | java -jar ASPECT.jar --beamer --resize 0.5
../_images/graph_coloring.png

Graph coloring solution generated with ASPECT graph mode.

N-queens Problem

The N-queens problem is a classic puzzle that involves placing N chess queens on an N x N chessboard such that no two queens threaten each other: so, no pair of queens should share the same row, column, or diagonal. The challenge is to find a solution for any given value of N.

We use an ASP encoding where the chessboard is described with an atom grid(I,J) for all the possible squares of the board, while the solution has an atom queen(R,C) indicating each queen positioned on the board.

#const n = 8.

1 { queen(I, 1..n) } 1 :- I = 1..n.
1 { queen(1..n, J) } 1 :- J = 1..n.

:- 2 { queen(I,J) : D = I+J+1 }, D = 1..2*n-1.
:- 2 { queen(I,J) : D = I-J+n }, D = 1..2*n-1.

The following two lines of ASPECT code draw the squares of the checkerboard, each with side length 2 and centered in (2I,2J). In particular, the first line set the background color to gray for half of the squares to create the classic chequered pattern.

aspect_rectangle(2*I-1,2*J-1,2*I+1,2*J+1,dark):- I = 1..n, J = 1..n, I\2=J\2.
aspect_rectangle(2*I-1,2*J-1,2*I+1,2*J+1,light):- I = 1..n, J = 1..n, I\2!=J\2.

aspect_style(dark, "fill", "gray").
aspect_style(light, "fill", "white").

In a similar fashion, we can draw the queens with:

aspect_imagenode(2*I,2*J,"./examples/02-n-queens/queen.png",queen):- queen(I,J).
aspect_style(queen, "width", 50).

It is a good idea to use layers to put the queens on top of the squares:

aspect_layer(dark, 0).
aspect_layer(light, 0).
aspect_layer(queen, 1).

Tip

To try this example (using clingo as ASP solver) run the following command:

clingo ./examples/02-n-queens/queens.lp | java -jar ASPECT.jar

If you want to draw 10 solutions use:

clingo ./examples/02-n-queens/queens.lp 10 | java -jar ASPECT.jar

If you want the 10 solutions drawn in a single beamer presentation try:

clingo ./examples/02-n-queens/queens.lp 10 | java -jar ASPECT.jar --beamer

the result in this last case is better by also setting the resize parameter

clingo ./examples/02-n-queens/queens.lp 10 | java -jar ASPECT.jar --beamer --resize 0.8
../_images/n_queens_8x8.png

N-queens problem (N = 8) solution generated with ASPECT.

Tower of Hanoi

The Tower of Hanoi is a well known example of planning problem in computer science. The Tower of Hanoi involves three pegs and a number of disks of different sizes that can slide onto any peg. The puzzle begins with the disks stacked on one peg in order of decreasing size, the smallest at the top. The challenge is to move the initial stack of disks from one peg to another, for any given number of disks, while following some rules.

  • Each move consists of taking the upper disk from a stack and placing it on top of another stack or an empty peg;

  • A move involves the movement of only one disk at a time;

  • It is not possible to place a disk on top of a smaller one.

The ASP encoding of the problem includes an atom peg(P) for each peg and an atom disk(D) for each disk. Moves are encoded by atoms on(D,P,T) representing the fact that disc D is on peg P at time T. The complete ASP encoding can be found on here.

The graphic animation depicting the entire sequence of moves to solve the problem is possible with the following lines of code:

% draw pegs
aspect_rectangle(X, 0, X+2, 18, pegs) :- peg(P), peg_x(P, X).

% draw disks
disk_level(Count, D1, P, T) :- on(D1, P, T), #count { D2 : on(D2, P, T), disk(D2), D2 < D1} = Count.

aspect_rectangle(X-Width, L*2, X+2+Width, (L*2)+2, s(fill,Color), T+1) :-
    on(D, P, T), peg(P), peg_x(P, X), disk_color(D, Color), disk_width(D, Width), disk_level(L, D, P, T).

% styles
aspect_style(pegs, "fill", "gray").
aspect_style(s(fill,C), fill, C) :- disk_color(_, C).

Note that the rectangles representing the pegs do not include the frame parameter since they are intended to be present throughout the entire animation. On the other hand, the disks have the frame parameter, and it corresponds to the variable T of the on(D,P,T) atom.

The previous code also depends on the following atoms introducing information regarding the graphical appearance of the various elements.

disk_width(1, 6).
disk_width(2, 4).
disk_width(3, 2).
disk_width(4, 1).
disk_color(1, red).
disk_color(2, green).
disk_color(3, blue).
disk_color(4, yellow).
peg_x(a, 6).
peg_x(b, 20).
peg_x(c, 34).

Tip

To try this example (using clingo as ASP solver) run the following command:

clingo ./examples/07-tower-of-hanoi/hanoi.lp | java -jar ASPECT.jar

this encoding is with 4 disks, so 16 files representing the sequence of moves (15 moves + initial position) are generated.

If you want the sequence drawn in a single beamer presentation try:

clingo ./examples/07-tower-of-hanoi/hanoi.lp | java -jar ASPECT.jar --beamer

To generate JavaScript driven PDFs containing vector graphics in motion, you can use the animate mode:

clingo ./examples/07-tower-of-hanoi/hanoi.lp | java -jar ASPECT.jar --animate
../_images/hanoi.gif

Sequence of moves to solve the Tower of Hanoi, with 4 disks (animated).

Note

More examples are available in the GitHub repository.