坚持在 Minizinc 中制作俄罗斯方块解算器

Question

我正在尝试在 Minizinc 中实现俄罗斯方块求解器，我想这也被称为 "packing" 问题。

我是 Minizinc 的新手，几乎不知道我在做什么，但我目前在我的代码中遇到了一个特定的限制。

我想通过在方块中放置 4 个 "l" 方块来解决一个 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 个 space 块，那么它的第一个块必须位于 x、y、y+1、y+2 和 y+3。

然而，即使有这个约束（以及我的所有其他约束），我仍然通过求解器得到类似这样的输出：

块甚至不应该放在第 2 行，因为它没有 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 型号；我已经制作了所述问题的小型工作版本。主要区别是：

使用 Parameters/Variables 而不是函数。（函数和谓词在 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];

该模型还未涵盖（well）：

棋盘上的空位。
方块的旋转。

坚持在 Minizinc 中制作俄罗斯方块解算器

Stuck making a Tetris solver in Minizinc

constraints

solver

constraint-programming

minizinc