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

这种模式还没有覆盖（井）：

• 在板空的地方。
• 旋转块。