I'm trying to implement a Tetris solver in Minizinc, which is also known as the "packing" problem I suppose.
I'm brand new to Minizinc and have barely any idea what I'm doing, but I'm currently stuck on a particular constraint in my code.
I am trying to solve a 4x4 square by placing 4 "l" blocks in Tetris into the square so that I will fill up the entire square.
My one major constraint is this:
constraint forall(b in 1..total) %default
(
forall(x,y in 1..n)
(
(Type(TypeOf[b], 1) /\ Loc(b,x,y) /\ Rot(b, 1) /\ not Ref(b) /\ (y+3<=n))
-> (Has(x,y,b) /\ Has(x,y+1,b) /\ Has(x,y+2,b) /\ Has(x,y+3,b))
)
);
This constraint is supposed to go through all of the provided blocks first (4 "l" blocks), then cycle through the actual board to find: If current block is of type 1 (type "l"), and its origin is placed at x,y, and it has a rotation of 1 (so no rotation in this case), and it's not reflected, and it has more than 3 blocks of space beneath it, then it must have the first block at x,y, y+1, y+2, and y+3.
However even with this constraint (and all my other constraints), I still get an output of something like this through the solver:
board:
4 4 4 4
3 2 2 2
2 1 1 1
1 3 3 3
loc:
0 0 0 0
1 1 1 1
0 0 0 0
0 0 0 0
Blocks aren't even supposed to be placed at the 2nd row because it does not have 3 blocks of clearing going down, and the board does not match up at all to the origin points, and does not match the above constraint of having blocks go straight down.
I am really out of ideas on how to fix this. On paper the logic seems sound, but I can't figure out where I went wrong. I will have my full code posted with all my other constraints. Please note yes I realize I currently only have the constraints for the "l" block in one orientation, but I am trying to solve it with 4 "l" blocks, which should fit just fine in that one orientation, so there's no reason why it should be outputting what it's outputting.
Thanks for any help guys.
include "globals.mzn";
include "builtins.mzn";
%Given variables
int: n; %length of board size
set of int: ROW = 1..n;
int: m=n; %number of columns
set of int: COL = 1..m;
%Number of starting tetrominoes
int: nR; %ID 1 for R
int: nS; %ID 2 for S
int: nT; %ID 3 for T
int: nL; %ID 4 for L
int: total = nR+nS+nT+nL;
array[int] of int: R = [ 1 | i in 1..nR];
array[int] of int: S = [ 2 | i in 1..nS];
array[int] of int: T = [ 3 | i in 1..nT];
array[int] of int: L = [ 4 | i in 1..nL];
array[int] of int: TypeOf = R++S++T++L; %Array of all blocks
%Decision Variables
array[1..n*n] of var 1..total: board; %Stored via (y-1)*n+x, using 1D array for ease of access.
array[1..n*n] of var 0..4: loc; %A separate location board that maps the origin point of each block
array[1..total] of var 1..4: rot; %Block rotations
array[1..total] of var 0..1: ref; %Block reflections
constraint total*4 == n*n;
constraint 0 <= nR /\ nR <= n /\ 0 <= nS /\ nS <= n /\ 0 <= nT /\ nT<= n /\ 0 <= nL /\ nL <= n;
constraint forall(i in 1..total)(TypeOf[i] == 1 \/ TypeOf[i] == 2 \/ TypeOf[i] ==3 \/ TypeOf[i] == 4);
constraint count(TypeOf, 1, nR)/\count(TypeOf,2,nS)/\count(TypeOf,3,nT)/\count(TypeOf,4,nL);
predicate Has(int: x, int: y, int: b) = board[(y-1)*n+x] == b;
predicate IsBlock(int: b) = b == 1 \/ b==2 \/ b==3 \/ b==4;
% BOARD RECORDS BLOCK NUMBER
% LOC RECORDS TYPE
predicate Loc(int: b, int: x, int: y) = loc[(y-1)*n+x] == TypeOf[b];
predicate Type(int: b, int: x) = b == x;
predicate Ref(int: i) = ref[i] == 1;
predicate Rot(int: i, int: amt) = rot[i] == amt;
%Block type 1 ----
constraint forall(b in 1..total) %default
(
forall(x,y in 1..n)
(
(Type(TypeOf[b], 1) /\ Loc(b,x,y) /\ Rot(b, 1) /\ not Ref(b) /\ (y+3<=n))
-> (Has(x,y,b) /\ Has(x,y+1,b) /\ Has(x,y+2,b) /\ Has(x,y+3,b))
)
);
% constraint forall(b in 1..total) %90 degrees counterclockwise
% (
% forall(x in 1..n)
% (
% forall(y in 1..n)
% (
% ((Type(Blocks[b], 1) /\ Loc(b,x,y) /\ Rot(b, 2) /\ not Ref(b) /\ (x+3<=n)) ->
% (Has(x,y,b) /\ Has(x+1,y,b) /\ Has(x+2, y, b) /\ Has(x+3, y, b)))
% )
% )
% );
% constraint forall(b in 1..total) %180 degrees counterclockwise
% (
% forall(x in 1..n)
% (
% forall(y in 1..n)
% (
% ((Type(Blocks[b], 1) /\ Loc(b,x,y) /\ Rot(b, 3) /\ not Ref(b) /\ (y-3>=1)) ->
% (Has(x,y,b) /\ Has(x,y-1,b) /\ Has(x, y-2, b) /\ Has(x, y-3, b)))
% )
% )
% );
% constraint forall(b in 1..total) %270 degrees counterclockwise
% (
% forall(x in 1..n)
% (
% forall(y in 1..n)
% (
% ((Type(Blocks[b], 1) /\ Loc(b,x,y) /\ Rot(b, 4) /\ not Ref(b) /\ (x-3>=1)) ->
% (Has(x,y,b) /\ Has(x-1,y,b) /\ Has(x-2, y, b) /\ Has(x-3, y, b)))
% )
% )
% );
% Make sure loc board doesn't have more blocks of each type than given
constraint count(loc, 1, nR)/\count(loc,2,nS)/\count(loc,3,nT)/\count(loc,4,nL);
% % Make sure each block in board is only used once
constraint forall(x in 1..total)(count(board, x, 4));
% Make sure board contains valid blocks
constraint forall(x in 1..n)
(
forall(y in 1..n)
(
exists(b in 1..4)(IsBlock(b) /\ Has(x,y,b))
)
);
solve satisfy;
output[
"board: \n"]++[
show(board[(c-1)*n+p]) ++
if p == n then "\n" else " " endif
| c in ROW, p in COL
]++[
"\n loc: \n"]++[
show(loc[(c-1)*n+p]) ++
if p == n then "\n" else " " endif
| c in ROW, p in COL
]
++["\n rot: \n" ++ show(rot)];
As you say it's your first MiniZinc model; I've made small working version of the stated problem. The main differences are:
MiniZinc Model:
%% Parameters
% Board
int: width = 4;
set of int: COLUMNS = 1..width;
int: height = 4;
set of int: ROWS = 1..height;
% Tetrominoes
int: nr_shapes = 1;
set of int: SHAPES = 1..nr_shapes;
int: nr_I_shapes = 4;
int: I = 1;
set of int: BLOCKS = 1..sum([nr_I_shapes]);
array[BLOCKS] of SHAPES: TYPE = [ I | x in 1..nr_I_shapes];
%% Variables
% Block location
array[BLOCKS] of var COLUMNS: loc_x;
array[BLOCKS] of var ROWS: loc_y;
% Board
array[COLUMNS, ROWS] of var BLOCKS: board;
%% Constraints
% I block constraint (Inclusive channeling)
constraint forall (b in BLOCKS)
(
if TYPE[b] = I then
board[loc_x[b], loc_y[b]] = b /\ board[loc_x[b]+1, loc_y[b]] = b /\
board[loc_x[b]+2, loc_y[b]] = b /\ board[loc_x[b]+3, loc_y[b]] = b
else
true
endif
);
solve satisfy;
output[
"board: \n"]++[
show(board[c,r]) ++
if c = width then "\n" else " " endif
| r in ROWS, c in COLUMNS
] ++ ["\nlocations:\n"] ++
[ "loc \(b): \(loc_x[b]), \(loc_y[b])\n" | b in BLOCKS];
This model does not yet cover (well):