Packing
(Main file name: packing)
Packing
is one of many problems that are tackled with constraint/logic
programming. Given a 4*4 grid board and 4 tetrominoes of the following
four types, is it possible to pack the board with the tetrominoes
such that no tetrominoes overlap each other and the board is
completely covered? Note that tetrominoes can be flipped and/or rotated before being put on the board.
Input Formats
An input file for LP systems contains the following four facts: r(R),
there are R number of R-tetrominoes; s(S), there are S number of
S-tetrominoes; t(T), there are T number of T-tetrominoes; and l(L),
there are L number of L-tetrominoes, where 0 ≤ R, S, T, L ≤ 4 and R+S+T+L = 4.
An input file for Minizinc specifies
the following constants: r, the number of R-tetrominoes; s, the number of
S-tetrominoes; t, the number of T-tetrominoes; l, the number of L-tetrominoes.
Output format
The output should be 'yes.' if the given number of tetrominoes can be packed into the 4*4 board, and 'no.' otherwise.
Samples
| LP Input | Minizinc Input | Output |
r(2).
s(2).
l(0).
t(0).
| r = 2;
s = 2;
l = 0;
t = 0;
| yes.
|
r(1).
s(0).
l(1).
t(2).
| r = 1;
s = 0;
l = 1;
t = 2;
| yes.
|
r(0).
s(0).
l(2).
t(2).
| r = 0;
s = 0;
l = 2;
t = 2;
| no.
|