Placing Squares using Prolog Reified CLP(FD)

Constraint logic programming provides intelligent search to Prolog. It is usually denoted by CLP(X), where X stands for some domain. For example CLP(B) is a constraint logic programming for boolean domain and CLP(FD) is constraint logic programming for finite domain.

The basic constraints in CLP(FD) are (#<)/2, (#>=)/2, etc.. in analogue to the ISO core standard arithmetic comparisons (<)/2, (>=)/2, etc .. In the following we will show how to code a tiling problem. We want to place squares 2x2, 3x3, 4x4 and 5x5 in a 9x7 box.

For this purpose we need to formulate that two rectangles are disjoint. A first attempt to formulate such a predicate in CLP(FD) might read using ordinary ISO core standard disjunction (;)/2. There is the disadvantage that the predicate lea point:

disjoint([XA1,XA2,YA1,YA2],[XB1,XB2,YB1,YB2]) :-
   XB1 #>= XA2; XA1 #>= XB2;
   YB1 #>= YA2; YA1 #>= YB2.

?- disjoint([1,3,5,7],[5,8,4,7]).
Yes ;
No

An advanced feature of CLP(FD) are so called reified constraints. Reified constraints allow to probe the boolean value of a constraint, for example 3 #< 4 #<==> B gives the value B=1. More importantly reified constraints allow to suspend disjunction and avoid choice points:

disjoint([XA1,XA2,YA1,YA2],[XB1,XB2,YB1,YB2]) :-
   XB1 #>= XA2 #\/ XA1 #>= XB2 #\/
   YB1 #>= YA2 #\/ YA1 #>= YB2.

?- disjoint([0,2,5,7],[5,8,4,7]).
Yes

In constraint programming choice points are later generated during labeling. The label/1 predicate has the advantage that it can analyze the given problem and that it can apply search strategies over the given problem. To solve the square placing problem we use the following

squares(L) :-
   maplist(square, [2,3,4,5], L),
   term_variables(L, V),
   place(L),
   label(V).

square(S, [X1,X2,Y1,Y2]) :-
   X1 in 0..8, X2 in 1..9,
   Y1 in 0..6, Y2 in 1..7,
   X2 #= X1+S, Y2 #= Y1+S.

place([]).
place([A|L]) :-
   place(L, A),
   place(L).

place([], _).
place([A|L], B) :-
   disjoint(A, B),
   place(L, B).

We have hardcoded that there are squares 2x2, 3x3, 4x4 and 5x5 in the form of a list [2,3,4,5] and the predicate square/2. We have also hardcoded that the given box is 9x7 in thatwe domain ranges X1 in 0..8, X2 in 1..9, Y1 in 0..6, Y2 in 1..7. The following screenshot shows an example run:



The example can be run in Jekejeke Prolog Minlog Extension, which provides the CLP(FD) solver or it can be run in another Prolog system. To display a solution we used a little further Prolog code. We simply iterate through the coordinates and check each coordinate point.

Jekejeke Prolog Minlog Extension
h tp // w w. 지케케. ch/이타 b/도 cぇt/p로 d/엔/도 cs/15_민/파c게. HTML

Open Source: Square Tiling
htps : // 기 st. 기주 b. 이 m/j부 r세/3아 dc다 7096d15f05 예 44287 아 db2