/*-------------------------------------------------------------------------*/
/* Benchmark (Finite Domain) */
/* */
/* Name : square.pl */
/* Title : perfect square */
/* Original Source: Pascal Van Hentenryck ([VHSD93]) */
/* Adapted by : Gregory Sidebottom (Nicolog) and Daniel Diaz (clp(FD)) */
/* Adapted by : Daniel Diaz for GNU Prolog */
/* Date : June 1994 */
/* */
/* This program solves the perfect square packing problem (SPP): find a way*/
/* to pack all the given squares (i.e. known sizes) into a master rectangle*/
/* so that none overlap and there is no wasted space. */
/* There are 4 instances of the problem (P=3 corresponds to [VSHD93]). */
/* */
/* Solution: */
/* 1 x([ 0, 0,18,22,23,15,15,18,22]) 2 x([ 0,41,42, 0,22,25,25,36,36,22]) */
/* y([ 0,18, 0,14,24,25,18,14,24]) y([ 0,23, 0,25,28, 0,17,17,23,25]) */
/* s([18,15,14,10, 9, 8, 7, 4, 1]) s([25,24,23,22,19,17,11, 6, 5, 3]) */
/* */
/* 3 x([ 0,70,75, 0,79,50 ,0,50,46,27,52,35,59,35,35,50,27,52,46,75,50]) */
/* y([ 0,70,33,50, 0, 0,85,29,88,93,70,65,54,50,82,54,85,63,82,29,63]) */
/* s([50,42,37,35,33,29,27,25,24,19,18,17,16,15,11, 9, 8, 7, 6, 4, 2]) */
/* */
/* 4 x([ 0,111, 0, 56, 81,132, 72, 0,140,142,111,81,111, 38, 38, 56, 58,*/
/* 63,132, 58, 59, 56,140, 58]) */
/* y([ 0,111, 81, 81, 0, 0,136,137, 43, 78, 80,51, 51,155,137,136,161,*/
/* 152, 43,156,152,152, 78,155]) */
/* s([ 81, 64, 56, 55, 51, 43, 39, 38, 35, 33, 31,30, 29, 20, 18, 16, 14,*/
/* 9, 8, 5, 4, 3, 2, 1]) */
/*-------------------------------------------------------------------------*/
q:- write('N ?'), read_integer(N), statistics(runtime,_),
square(N,Xs,Ys,Ss), statistics(runtime,[_,Y]),
write(x(Xs)), nl, write(y(Ys)), nl, write(s(Ss)), nl,
write('time : '), write(Y), nl.
problem(1,32,33,[18,15,14,10,9,8,7,4,1]).
problem(2,65,47,[25,24,23,22,19,17,11,6,5,3]).
problem(3,112,112,
[50,42,37,35,33,29,27,25,24,19,18,17,16,15,11,9,8,7,6,4,2]).
problem(4,175,175,
[81,64,56,55,51,43,39,38,35,33,31,30,29,20,18,16,14,9,8,5,4,3,2,1]).
square(P,Xs,Ys,Ss):-
gen(P,Xs,Ys,Ss,SX,SY),
(SX>=SY -> MaxS=SX
; MaxS=SY),
fd_set_vector_max(MaxS),
no_overlap(Xs,Ys,Ss),
cap(Xs,Ss,SX,SY),
cap(Ys,Ss,SY,SX),
label(Xs),
label(Ys).
gen(P,Xs,Ys,Ss,SX,SY):-
problem(P,SX,SY,Ss),
gen_coords(Ss,Xs,Ys,SX,SY).
gen_coords([],[],[],_,_).
gen_coords([S|Ss],[X|Xs],[Y|Ys],SX,SY):-
X #=< SX-S,
Y #=< SY-S,
gen_coords(Ss,Xs,Ys,SX,SY).
no_overlap([],[],[]).
no_overlap([X|Xs],[Y|Ys],[S|Ss]):-
no_overlap1(Xs,Ys,Ss,X,Y,S),
no_overlap(Xs,Ys,Ss).
no_overlap1([],[],[],_,_,_).
no_overlap1([X2|Xs],[Y2|Ys],[S2|Ss],X1,Y1,S1):-
X1+S1 #=< X2 #\/ X1 #>= X2+S2 #\/ Y1+S1 #=< Y2 #\/ Y1 #>= Y2+S2,
no_overlap1(Xs,Ys,Ss,X1,Y1,S1).
cap(Xs,Ss,SX,SY):-
cap1(0,SX,SY,Xs,Ss).
cap1(P,SX,SY,Xs,Ss):-
(P < SX -> sum_of_squares_with(Xs,Ss,P,SY),
P1 is P+1,
cap1(P1,SX,SY,Xs,Ss)
;
true).
sum_of_squares_with([],[],_,0).
sum_of_squares_with([X|Xs],[S|Ss],P,Sum):-
point_used_by_square_iff_b(P,X,S,B),
Sum #= S*B+Sum1,
sum_of_squares_with(Xs,Ss,P,Sum1).
% X<=P<X+S <=> B P and S are ground
point_used_by_square_iff_b(P,X,S,B):-
B #<=> X #=< P #/\ P #< X+S.
label([]).
label([X|Xs]):-
list_min([X|Xs],Min),
select_square([X|Xs],Min,Rest),
label(Rest).
list_min([X|Xs],Min):-
fd_min(X,Min1),
list_min1(Xs,Min1,Min).
list_min1([],M,M).
list_min1([X|Xs],M1,M):-
fd_min(X,M2),
(M1=<M2 -> M3=M1
; M3=M2),
list_min1(Xs,M3,M).
select_square([X|Xs],X,Xs).
select_square([X|Xs],Min,[X|Rest]):-
X#>Min,
select_square(Xs,Min,Rest).
:- initialization(q).
