Next: CLPQR Monash Examples, Previous: CLPQR Projection, Up: lib-clpqr [Contents][Index]
A beautiful example of disequations at work is due to [Colmerauer
90]. It addresses the task of tiling a rectangle with squares of
all-different, a priori unknown sizes. Here is a translation of the
original Prolog-III program to clp(Q,R):
% library('clpqr/examples/squares')
filled_rectangle(A, C) :-
{ A >= 1 },
distinct_squares(C),
filled_zone([-1,A,1], _, C, []).
distinct_squares([]).
distinct_squares([B|C]) :-
{ B > 0 },
outof(C, B),
distinct_squares(C).
outof([], _).
outof([B1|C], B) :-
{ B =\= B1 }, % *** note disequation ***
outof(C, B).
filled_zone([V|L], [W|L], C0, C0) :-
{ V=W,V >= 0 }.
filled_zone([V|L], L3, [B|C], C2) :-
{ V < 0 },
placed_square(B, L, L1),
filled_zone(L1, L2, C, C1),
{ Vb=V+B },
filled_zone([Vb,B|L2], L3, C1, C2).
placed_square(B, [H,H0,H1|L], L1) :-
{ B > H, H0=0, H2=H+H1 },
placed_square(B, [H2|L], L1).
placed_square(B, [B,V|L], [X|L]) :-
{ X=V-B }.
placed_square(B, [H|L], [X,Y|L]) :-
{ B < H, X= -B, Y=H-B }.
There are no tilings with less than nine squares except the trivial one where the rectangle equals the only square. There are eight solutions for nine squares. Six further solutions are rotations of the first two.
clp(q) ?- [library('clpqr/examples/squares')].
clp(q) ?- filled_rectangle(A, Squares).
A = 1,
Squares = [1] ? ;
A = 33/32,
Squares = [15/32,9/16,1/4,7/32,1/8,7/16,1/32,5/16,9/32] ? ;
A = 69/61,
Squares = [33/61,36/61,28/61,5/61,2/61,9/61,25/61,7/61,16/61] ? RET
Depending on your hardware, the above query may take a few minutes. Supplying the knowledge about the minimal number of squares beforehand cuts the computation time by a factor of roughly four:
clp(q) ?- length(Squares, 9), filled_rectangle(A, Squares).
A = 33/32,
Squares = [15/32,9/16,1/4,7/32,1/8,7/16,1/32,5/16,9/32] ? ;
A = 69/61,
Squares = [33/61,36/61,28/61,5/61,2/61,9/61,25/61,7/61,16/61] ? RET