Contents
ToggleConstraint logic programming
This page presents detailed corrected exercises of the problem of logic programming by constraints, which is a natural mix of logic programming and constraint programming.
Exercise 1
Consider the following puzzle:
Each region of the grid must be filled with a number between 0 and 9 so that
- the numbers in two adjacent regions (vertically or horizontally) are different
- whenever there are four regions that meet at a point (indicated by a small circle), the sum of their numbers is equal to 20.
Solve this problem by constraint logic programming.
Let's name from top left to bottom right (by line) the empty squares by a letter. Each domain has a value between 0 and 9. Thereafter, the two constraints must be filled in manually.
For each square, its score must be different from its neighbours.
For each circle, the sum must be equal to 20.
We therefore have the following constraint logic programming:
L = [A,B,C,D,E,F,G,H,I,J,K,M],
L::[0..9],
At #\= 7, At #\= 8, At #\= 6,
B #\= 8, B #\= 4,
C #\= 7, C #\= 6, C #\= 9,
D #\= 6, D #\= 8,
E #\= 6, E #\= 8, E #\= 4, E #\= 5,
F #\= 9, F #\= 6, F #\= G, F #\= Y,
G #\= 6, G #\= 5, G #\= K,
H #\= 5, H #\= 4, H #\= M,
I #\= 9, I #\= J, J #\= K,
K #\= 5, K #\= M,
7+6+A+C #= 20, A+6+8+D #= 20, 6+8+D+E #= 20, 4+8+B+E #= 20,
9+6+C+F #= 20, 5+6+E+G #= 20, 4+5+E+H #= 20,
9+F+I+J #= 20, F+G+J+K #= 20, 5+H+K+M #= 20,
labeling(L).
Exercise 2
Consider the game Bokkusu. The object of the game is to mark certain squares of the given grid in black.
Each box has two values: an A value and a B value. The numbers on the right denote the A values of the boxes in each corresponding row and the numbers at the bottom denote the B values of the boxes in each corresponding column (These values always range from 1 to the size of the grid by increasing by 1 from left to right or from top to bottom).
The values on the left indicate the sum of the B values of the black boxes for each row and the values on the top indicate the sum of the A values of the black boxes for each column. An example of a grid and its solution is given in the figure. In the solution of this example we have for example 7 = 1 + 2 + 4 (the boxes with B value of 1, 2 and 4 are marked black) and 6 = 2 + 4 (the boxes with A values of 2 and 4 are marked).
Solve this problem by constraint logic programming.
Let's name each square in the grid in a matrix fashion. For the constraints, the sum of the binary variables (white=0 or black=1) multiplied by the coefficients on the left or on the top must be equal to the value opposite.
L = [X11,X12,X13,X14,
X21,X22,X23,X24,
X31,X32,X33,X34,
X41,X42,X43,X44],
fd_domain(L,0,1),
X11 + 2*X12 + 3*X13 + 4*X14 #= 3,
X21 + 2*X22 + 3*X23 + 4*X24 #= 7,
X31 + 2*X32 + 3*X33 + 4*X34 #= 1,
X41 + 2*X42 + 3*X43 + 4*X44 #= 2,
X11 + 2*X21 + 3*X31 + 4*X41 #= 5,
X12 + 2*X22 + 3*X32 + 4*X42 #= 6,
X13 + 2*X23 + 3*X33 + 4*X43 #= 1,
X14 + 2*X24 + 3*X34 + 4*X44 #=2
Exercise 3
We consider the problem of generating a timetable. There are 7 classes and 4 slots. A slot can accommodate a maximum of 2 lessons. There are the following constraints:
– Course 4 must be before course 6.
– Course 5 must be before course 7.
– Course 6 must be before course 2.
– Course 1 cannot be in parallel with courses 2, 3, 4 and 7.
– Course 2 cannot be in parallel with courses 3 and 6.
– Course 3 cannot be in parallel with courses 4, 5 and 6.
– Course 4 cannot be in parallel with courses 5 and 6.
– Course 5 cannot be in parallel with course 7.
Solve this problem by constraint logic programming.
We will consider that the courses are domains, and that they can take a value from 1 to 4 corresponding to the niche that will be chosen. Constraint logic programming is as follows:
L = [C1,C2,C3,C4,C5,C6,C7],
fd_domain(L,1,4),
C4 #< C6, C5 #< C7, C6 #< C2,
C1 #\= C2, C1 #\= C3, C1 #\= C4, C1 #\= C7,
C2 #\= C3, C2 #\= C6,
C3 #\= C4, C3 #\= C5, C3 #\= C6,
C4 #\= C5, C4 #\= C6,
C5 #\= C7,
fd_cardinality(1,[C1#=1,C2#=1,C3#=1,C4#=1,C5#=1,C6#=1,C7#=1],2),
fd_cardinality(1,[C1#=2,C2#=2,C3#=2,C4#=2,C5#=2,C6#=2,C7#=2],2),
fd_cardinality(1,[C1#=3,C2#=3,C3#=3,C4#=3,C5#=3,C6#=3,C7#=3],2),
fd_cardinality(1,[C1#=4,C2#=4,C3#=4,C4#=4,C5#=4,C6#=4,C7#=4],2),
fd_labeling(L)
Exercise 4
Inshi no heya is a Japanese logic game. It is played on a rectangular grid of cells which are separated into rectangles. One dimension of each rectangle is 1 while the other dimension varies.
Each rectangle is placed horizontally or vertically and contains a number. The goal is to
fill all cells with numbers from 1 to 9 so that:
– If we multiply all the digits of each rectangle we obtain the number indicated in the rectangle
– No number appears more than once in a column.
– No number appears more than once in a line.
An example of an original grid and a solution are given below:
Solve this problem by constraint logic programming.
Each box of the matrix is considered as a domain, each box can take a value from 1 to 5. The constraints are simple since the sum of the boxes of a certain perimeter must be equal to a given number.
L = [X11,X21,X31,X41,X51,
X12,X22,X32,X42,X52,
X13,X23,X33,X43,X53,
X14,X24,X34,X44,X54,
X15,X25,X35,X45,X55],
fd_domain(L,1,9),
fd_all_different([X11,X12,X13,X14,X15]),
fd_all_different([X21,X22,X23,X24,X25]),
fd_all_different([X31,X32,X33,X34,X35]),
fd_all_different([X41,X42,X43,X44,X45]),
fd_all_different([X51,X52,X53,X54,X55]),
fd_all_different([X11,X21,X31,X41,X51]),
fd_all_different([X12,X22,X32,X42,X52]),
fd_all_different([X13,X23,X33,X43,X53]),
fd_all_different([X14,X24,X34,X44,X54]),
fd_all_different([X15,X25,X35,X45,X55]),
X11 #= 5, X31*X41 #= 2, X32*X42 #= 4, X33 #= 4,
X43*X53 #= 15, X34*X44 #= 15, X15*X25*X35*X45 #= 120,
X21*X22 #= 15, X51*X52 #= 12, X12*X13*X14 #= 8,
X23*X24 #= 2, X54*X55 #= 2,
fd_labeling(L)
Exercise 5
Skyscrapers are built on an NxN grid. Each skyscraper has a number of floors corresponding to its size (from 1 to N). In each column and each row each size appears exactly once. The numbers on the edges of the grid indicate how many skyscrapers can be seen when looking from that point towards the corresponding row or column. A skyscraper is visible if all the skyscrapers in front of it are smaller. Here is an example of a grid and its solution:
For example, in the second line from the bottom looking from the left we can see 2 skyscrapers: the one of height 3 and the one of height 4. Here is a second problem of a grid (5×5) to solve:
Solve this problem by constraint logic programming.
You can use the predefined predicate fd_cardinality(+List, ?Count)
where List is a list of constraints and Count is the number of List constraints satisfied.
constraint([A1,A2,A3,A4,A5],C):-
fd_cardinality([A5 #>A4 #/\A5 #>A3 #/\A5 #>A2 #/\A5 #>A1,
A4 #>A3 #/\A4 #>A2 #/\A4 #>A1,
A3 #> A2 #/\A3 #> A1, A2 #> A1],C).
skyscraper(L):-
L = [Line1,Line2,Line3,Line4,Line5],
Line1 = [X11,X12,X13,X14,X15],
Line2 = [X21,X22,X23,X24,X25],
Line3 = [X31,X32,X33,X34,X35],
Line4 = [X41,X42,X43,X44,X45],
Line5 = [X51,X52,X53,X54,X55],
fd_domain(Line1,1,5),fd_domain(Line2,1,5),
fd_domain(Line3,1,5),fd_domain(Line4,1,5),
fd_domain(Line5,1,5),
fd_all_different(Line1),fd_all_different(Line2),
fd_all_different(Line3), fd_all_different(Line4),
fd_all_different(Line5),
fd_all_different([X11,X21,X31,X41,X51]),
fd_all_different([X12,X22,X32,X42,X52]),
fd_all_different([X13,X23,X33,X43,X53]),
fd_all_different([X14,X24,X34,X44,X54]),
fd_all_different([X15,X25,X35,X45,X55]),
% The first skyscraper is still visible. So you have to remove 1
% of each number of visible skyscrapers.
constraint(Line1,0), constraint(Line2,3), constraint(Line3,2),
constraint(Line4,1),
constraint([X12,X22,X32,X42,X52],2),
constraint([X13,X23,X33,X43,X53],2),
constraint([X15,X14,X13,X12,X11],2),
constraint([X25,X24,X23,X22,X21],1),
constraint([X35,X34,X33,X32,X31],2),
constraint([X55,X54,X53,X52,X51],0),
constraint([X52,X42,X32,X22,X12],1),
constraint([X53,X43,X33,X23,X13],1),
constraint([X54,X44,X34,X24,X14],1),
constraint([X55,X45,X35,X25,X15],0),
fd_labeling(Line1),fd_labeling(Line2),fd_labeling(Line3),
fd_labeling(Line4),fd_labeling(Line5).