/* 

  Box packing problem in Picat.

  This is a port of the B-Prolog's example clpfd/box.pl.
  """
  Purpose: Solve the box packing problem.
  Author: Neng-Fa Zhou, 2002
  Platform: B-Prolog 6.1 or up

  Description:

  The dimensions of the boxes are give by the relation box/1
  and the layout area is defined by the predicate area/2.
  For each box, let W and H be the width and the height box, 
  respectively, and AreaW and AreaH be the width and height 
  of the layout area, respectively. The domain of positions
  for the box is:
    
     [(0,0),...,(AreaW-W,AreaH-H)]

  """

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

% import util.
import cp.

main => go.


go =>
    Boxes = findall($box(W,H,_), box(W,H)),  %box(Width,Height,PosVar)
    area(AreaW,AreaH),  % layout area
    createPosVars(Boxes,AreaW,AreaH,PosVars),
    solve(PosVars),
    writeln(Boxes).


createPosVars([],_AreaW,_AreaH,B) ?=> B = [].
createPosVars(B,AreaW,AreaH,P) =>
    B = [$box(W,H,(PosX,PosY))|Boxes],
    P = [PosX,PosY|PosVars],
    PosX :: 0..AreaW-W,
    PosY :: 0..AreaH-H,
    notOverlap(W,H,PosX,PosY,Boxes),
    createPosVars(Boxes,AreaW,AreaH,PosVars).

notOverlap(_W,_H,_X,_Y,B) ?=> B=[].
notOverlap(W,H,X,Y,B) => 
    B=[$box(W1,H1,(X1,Y1))|Boxes],
    (X+W #=< X1 #\/ X1+W1 #=< X #\/ Y+H #=< Y1 #\/ Y1+H1 #=< Y),
    notOverlap(W,H,X,Y,Boxes).

index(-,-)
area(33,24).
% area(A,B) => A=33, B=24.

index(-,-)
box(3,9).
box(6,6).
box(9,6).
box(9,3).
box(12,3).
box(12,6).
box(3,12).
box(6,9).
box(6,12).
box(6,3).
box(21,3).
box(9,9).
box(3,18).