Stuck在Minizinc中製作俄羅斯方塊解算器

Question

我試圖在Minizinc中實現Tetris解算器，這也被稱爲「包裝」問題。

我是Minizinc的全新品牌，幾乎沒有任何想法，我正在做什麼，但我目前堅持在我的代碼中的特定約束。

我想通過將4個「l」塊放入廣場上的俄羅斯方塊來解決一個4×4的方塊，這樣我就可以填滿整個廣場。

我的一個主要制約因素是：

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處具有第一個塊。

然而即使有這樣的約束（以及我的所有其他約束），我仍然可以通過解算得到的是這樣的輸出：

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」塊的約束，但我正在試圖用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]; 

這種模式還沒有覆蓋（井）：

• 在板空的地方。
• 旋轉塊。