Minizinc에서 Tetris 솔버 만들기 멈춤

Question

Minizinc에서 Tetris 솔버를 구현하려고합니다. 이는 내가 생각하는 "패킹"문제라고도합니다.

저는 Minizinc에서 처음 접했고 현재 내가하고있는 일을 거의 이해하지 못했지만 현재는 코드의 특정 제약 조건을 고수하고 있습니다.

저는 4x4 사각형을 테트리스의 사각형에 4 개 배치하여 전체 사각형을 채울 수 있도록 4x4 사각형을 해결하려고합니다.

이 제약 조건이 먼저 제공하는 모든 블록을 통과하도록되어

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)) 
) 
); 

(4 "L"블록), 다음 실제 보드를 통해주기를 확인하는 방법은 다음과 같습니다 : 만약

내 하나 개의 큰 제약이있다 현재 블록은 유형 1 (유형 "l")이고 원점은 x, y에 있고 1의 회전 (이 경우 회전이 없음)이며 반사되지 않으며 3보다 큰 그 아래에 공간 블록이 있다면 x, y, y + 1, y + 2 및 y + 3에서 첫 번째 블록을 가져야합니다.

그러나 심지어이 제약 (내 모든 다른 제약), 난 아직도 솔버를 통해이 같은의 출력을 얻을과 :

블록은도 2 행에 배치되지 않는 것으로

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 

왜냐하면 그것은 3 블록의 클리어링을 가지지 않기 때문에 보드는 원점과 전혀 일치하지 않기 때문에 블록을 똑바로 세우는 위의 제약 조건과 일치하지 않습니다.

저는이 문제를 해결하는 방법에 대한 아이디어가 없습니다. 논문에서 논리적 인 것처럼 보이지만 어디서 잘못되었는지 알 수는 없습니다. 내 모든 다른 제약 조건과 함께 전체 코드를 게시 할 것입니다. 유의하십시오. 저는 현재 하나의 방향에서 "l"블록에 대한 제약 조건 만 가지고 있음을 알고 있습니다. 그러나 "I"블록을 4 개의 "l"블록으로 해결하려고합니다. 이것은 한 방향으로 잘 맞아야하는데 이유가 없습니다. 출력중인 내용을 출력해야합니다.

도움 주셔서 감사합니다.

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)]; 

Answer 1

여러분이 처음 말하는 MiniZinc 모델입니다. 나는 명시된 문제의 작은 작업 버전을 만들었습니다. 주요 차이점은 다음과 같습니다.

• 기능 대신 매개 변수/변수 사용. (함수 및 술어는 MiniZinc에서 배열 액세스를 사용하지 않고 더 복잡한 개념을 표현하는 데 사용됩니다.)
• 요소 제약 조건을 사용하여 위치 및 보드 변수를 통합합니다.
• 중복 변수 제거 (일부는 무엇을했는지 몰랐습니다).

MiniZinc 모델 :

%% 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]; 

이 모델은 아직 (잘) 적용되지 않습니다 보드에

• 빈 곳.
• 블록 회전.