N Rectangles inside the Square (Minizinc)

Question

I try to place N rectangular blocks with different sizes into a grid, by formulating it as a CSP problem.

The blocks should not overlap with each other, they can touch on the edges, and there can be empty places.

with requirement place 4 rectangular blocks of size 2x2 into a 8x8 grid.

I also need to generalize for varying the number of blocks, the sizes of the blocks, and the size of the grid. I dont understand how I use this terms in codes.

include "globals.mzn";

int: nParts;
set of int: PARTS = 1..nParts;

int: nShapes; 
set of int: SHAPES = 1..nShapes;

int: plateLength;
int: plateWidth;

set of int: LEN = 0..plateLength;
set of int: WID = 0..plateWidth;

int: k = 2;
set of int: DIM = 1..k;

array[SHAPES,DIM] of int: rect_size;
array[SHAPES,DIM] of 0..0: rect_offset;
array[PARTS] of set of SHAPES: shape;

array[PARTS,DIM] of var int: xy;
array[PARTS] of var SHAPES: kind;

constraint geost(k, rect_size, rect_offset, shape, xy, kind);

constraint forall(i in PARTS)(kind[i] in shape[i]);

constraint forall(i in PARTS)(xy[i,1] in LEN);
constraint forall(i in PARTS)(xy[i,1] + rect_size[kind[i], 1] in LEN);

constraint forall(i in PARTS)(xy[i,2] in WID);
constraint forall(i in PARTS)(xy[i,2] + rect_size[kind[i], 2] in WID);

What is your question about this? Does the model don't work? — hakank, Dec 26 '21 at 07:17
Actually I cant figure out how I use minizinc for this problem. Do you write codes for this CSP problem? — Promise89, Dec 26 '21 at 07:50
One model to solve your problem using the `geost` constraint can be found here: https://stackoverflow.com/q/60618751/5730444 — Phonolog, Jan 05 '22 at 15:57

score 2 · Answer 1 · answered Dec 26 '21 at 08:39

2

First of all you should use diffn global constraint that is specially suited for this kind of problems. I think it has stronger propagation than geost. Second, if you use geost use a solver that support it natively (JaCoP, Choco or Sicstus).

Check also benchmark perfect_square form this year minizinc chgallenge.

answered Dec 26 '21 at 08:39

Krzysztof Kuchcinski

121
1
1

You mean all differenr and related constraints https://www.minizinc.org/doc-2.5.5/en/lib-globals.html#all-different-and-related-constraints . How I use this constraints Can you give more detail I am new on minizinc – Promise89 Dec 26 '21 at 13:25

N Rectangles inside the Square (Minizinc)

1 Answers1