#### 10.35.6 Why Disequations

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>

Send feedback on this subject.