0

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

我是 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 块空间，那么它必须在 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)];
4

1 回答 1

0

正如您所说，这是您的第一个 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];

该模型尚未涵盖（很好）：

  • 棋盘上的空位。
  • 块的旋转。
于 2016-12-05T19:05:30.347 回答