Prolog约束处理:装箱正方形

Question

我正在尝试用prolog解决一个约束处理问题。

我需要在一个10x10的网格中打包4个5x5,4x4,3x3和2x2的正方形。它们不能重叠。

我的变量如下所示：

Name: SqX(i), i=1..10, domain: 1..10

其中X是5、4、3或2。索引i表示网格中的行、域和列。

我的第一个约束是定义正方形的宽度和高度。我将其表述如下：

Constraint: SqX(i) > SqX(j)-X /\ i>j-X, range: i>0 /\ j>0

因此，可能的点被约束为彼此之间在X行和X列之内。然而，Prolog在这些约束上停止，并给出以下结果：

Adding constraint "(Sq5_I > Sq5_J-5) /\ (I>J-5)" for values:
        I=1, J=1, 
        I=1, J=2, 
        I=1, J=3, 
        I=1, J=4, 
        I=1, J=5, 
        I=1, J=6, 
=======================[ End Solutions ]=======================

所以它就到此为止了，甚至不检查其他的方块。我的约束很可能太紧了，但我看不出为什么或如何。有什么建议吗？

Answer 1

对于每个正方形，定义表示左上角的X和Y变量。这些变量将具有域1..10-L，其中L是正方形的长度。如果将域设置为1..10，则正方形可能会部分放置在10x10矩形之外。

然后，您可以为每对矩形(X,Y)和(X1,Y1)发布约束，声明如果它们在x轴上重叠，则它们在y轴上不能重叠，反之亦然：

(((X  #=< X1) and (X+L   #> X1)) => ((Y+L #=< Y1) or (Y1+L1 #=< Y))),
(((X1 #=< X)  and (X1+L1 #> X))  => ((Y+L #=< Y1) or (Y1+L1 #=< Y))),
(((Y  #=< Y1) and (Y+L   #> Y1)) => ((X+L #=< X1) or (X1+L1 #=< X))),
(((Y1 #=< Y)  and (Y1+L1 #> Y))  => ((X+L #=< X1) or (X1+L1 #=< X)))

(您的特定约束语法可能会有所不同)

Answer 2

从3.8.3版本开始，SICStus Prolog提供了许多专门的placement constraints，可以很好地解决您的打包问题。特别是，由于您的装箱问题是二维的，您应该考虑使用disjoint2/1约束。

下面的代码片段使用disjoint2/1来表示矩形是不重叠的。主要关系是area_boxes_positions_/4。

:- use_module(library(clpfd)).
:- use_module(library(lists)).

area_box_pos_combined(W_total*H_total,W*H,X+Y,f(X,W,Y,H)) :-
    X #>= 1,
    X #=< W_total-W+1,
    Y #>= 1,
    Y #=< H_total-H+1.

positions_vars([],[]).
positions_vars([X+Y|XYs],[X,Y|Zs]) :-
    positions_vars(XYs,Zs).

area_boxes_positions_(Area,Bs,Ps,Zs) :-
    maplist(area_box_pos_combined(Area),Bs,Ps,Cs),
    disjoint2(Cs),
    positions_vars(Ps,Zs).

接下来是一些问题！首先，您的初始打包问题：

?- area_boxes_positions_(10*10,[5*5,4*4,3*3,2*2],Positions,Zs),
   labeling([],Zs).
Positions = [1+1,1+6,5+6,5+9],
Zs        = [1,1,1,6,5,6,5,9] ? ...

接下来，让我们最小化放置所有正方形所需的总面积：

?- domain([W,H],1,10),
   area_boxes_positions_(W*H,[5*5,4*4,3*3,2*2],Positions,Zs),
   WH #= W*H,
   minimize(labeling([ff],[H,W|Zs]),WH).
W         = 9,
H         = 7,
Positions = [1+1,6+1,6+5,1+6],
Zs        = [1,1,6,1,6,5,1,6],
WH        = 63 ? ...

可视化解决方案

单独的解决方案到底是什么样子的？ImageMagick可以生成漂亮的小位图……

下面是一些用于转储适当的ImageMagick命令的快速代码：

:- use_module(library(between)).
:- use_module(library(codesio)).

drawWithIM_at_area_name_label(Sizes,Positions,W*H,Name,Label) :-
    Pix = 20,

    % let the ImageMagick command string begin
    format('convert -size ~dx~d xc:skyblue', [(W+2)*Pix, (H+2)*Pix]),

    % fill canvas 
    format(' -stroke none -draw "fill darkgrey rectangle ~d,~d ~d,~d"', 
           [Pix,Pix, (W+1)*Pix-1,(H+1)*Pix-1]),

    % draw grid
    drawGridWithIM_area_pix("stroke-dasharray 1 1",W*H,Pix),

    % draw boxes
    drawBoxesWithIM_at_pix(Sizes,Positions,Pix),

    % print label
    write( ' -stroke none -fill black'),
    write( ' -gravity southwest -pointsize 16 -annotate +4+0'),
    format(' "~s"',[Label]),

    % specify filename
    format(' ~s~n',[Name]).

上面的drawWithIM_at_area_name_label/5代码依赖于两个小帮助器：

drawGridWithIM_area_pix(Stroke,W*H,P) :-   % vertical lines
    write(' -strokewidth 1 -fill none -stroke gray'),
    between(2,W,X),
    format(' -draw "~s path \'M ~d,~d L ~d,~d\'"', [Stroke,X*P,P, X*P,(H+1)*P-1]),
    false.
drawGridWithIM_area_pix(Stroke,W*H,P) :-   % horizontal lines
    between(2,H,Y),
    format(' -draw "~s path \'M ~d,~d L ~d,~d\'"', [Stroke,P,Y*P, (W+1)*P-1,Y*P]),
    false.
drawGridWithIM_area_pix(_,_,_).

drawBoxesWithIM_at_pix(Sizes,Positions,P) :-
    Colors = ["#ff0000","#00ff00","#0000ff","#ffff00","#ff00ff","#00ffff"],
    write(' -strokewidth 2 -stroke white'),
    nth1(N,Positions,Xb+Yb),
    nth1(N,Sizes,    Wb*Hb),
    nth1(N,Colors,   Color),
    format(' -draw "fill ~sb0 roundrectangle ~d,~d ~d,~d ~d,~d"',
           [Color, Xb*P+3,Yb*P+3, (Xb+Wb)*P-3,(Yb+Hb)*P-3, P/2,P/2]),
    false.
drawBoxesWithIM_at_pix(_,_,_).

使用可视化工具

让我们使用以下两个查询来生成一些静态图像。

?- drawWithIM_at_area_name_label([5*5,4*4,3*3,2*2],[1+1,6+1,6+5,1+6],9*7,
                                 'dj2_9x7.gif','9x7').

?- drawWithIM_at_area_name_label([5*5,4*4,3*3,2*2],[1+1,1+6,5+6,5+9],10*10,
                                 'dj2_10x10.gif','10x10').

让我们使用以下hack-query为上述矩形在大小为9*7的棋盘上的放置的每个解决方案生成一个图像

?- retractall(nSols(_)), 
   assert(nSols(1)), 
   W=9,H=7,
   Boxes = [5*5,4*4,3*3,2*2],
   area_boxes_positions_(W*H,Boxes,Positions,Zs),
   labeling([],Zs), 
   nSols(N), 
   retract(nSols(_)), 
   format_to_codes('dj2_~5d.gif',[N],Name),
   format_to_codes('~dx~d: solution #~d',[W,H,N],Label),
   drawWithIM_at_area_name_label(Boxes,Positions,W*H,Name,Label),
   N1 is N+1,
   assert(nSols(N1)),
   false.

接下来，执行上述查询输出的所有ImageMagick命令。

最后，使用ImageMagick构建第三个查询的解决方案集的动画：

$ convert -delay 15  dj2_0.*.gif   dj2_9x7_allSolutions_1way.gif 
$ convert dj2_9x7_allSolutions_1way.gif -coalesce -duplicate 1,-2-1 \
          -quiet -layers OptimizePlus -loop 0 dj2_9x7_allSolutions.gif

结果

首先，10*10电路板尺寸的一种解决方案：

​

其次，对于最小尺寸(9*7)的电路板，有一种解决方案：

​

最后，最小尺寸(9*7)的电路板的所有解决方案：

​

编辑2015-04-14

从7.1.36版本开始，SWI-Prolog clpfd library支持constraint disjoint2/1。

编辑2015-04-22

下面是一个基于tuples_in/2约束的替代实现的草图：

每对长方体的

1. 确定这两个不重叠的所有位置。
2. 将有效组合编码为元组列表。每对长方体的
3. 发布一个tuples_in/2约束。

作为一个私人的概念验证，我实现了一些遵循这个想法的代码；就像@CapelliC在他的回答中一样，我得到了169480运算符声明的盒子和板子大小的不同解决方案。

运行时间可与其他基于clp(FD)的答案相媲美；事实上，它对于较小的电路板(10*10或更小)非常有竞争力，但对于较大的电路板尺寸会变得更差。

请承认，为了正派起见，我不会张贴代码：)

Answer 3

这里已经发布了几个很好的解决方案(所有人+1！)，使用CLP(FD)约束。

此外，我想展示一种概念上不同的方法来解决这种布局和覆盖任务，使用CLP(B)约束。

其思想是将瓦片的每个可能位置视为网格上特定元素处的一组TRUE值，其中每个网格元素对应于矩阵的一列，并且瓦片的每个可能位置对应于一行。然后，任务是以这样的方式选择所述矩阵的一组行，即每个网格元素至多被覆盖一次，或者换句话说，在由所选行组成的子矩阵的每一列中至多有一个真值。

在这个公式中，行的选择-以及因此在特定位置的瓦片的放置-由布尔变量表示，每个变量对应于矩阵的每一行。

这是我想要分享的代码，它在SICStus Prolog和SWI中工作，只需稍作修改即可：

:- use_module(library(clpb)).
:- use_module(library(clpfd)).

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   The tiles we have available for placement.

   For example, a 2x2 tile is represented in matrix form as:

       [[1,1],
        [1,1]]

   1 indicates which grid elements are covered when placing the tile.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

tile(5*5).
tile(4*4).
tile(3*3).
tile(2*2).

tile_matrix(Rows) :-
        tile(M*N),
        length(Rows, M),
        maplist(length_list(N), Rows),
        append(Rows, Ls),
        maplist(=(1), Ls).

length_list(L, Ls) :- length(Ls, L).

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   Describe placement of tiles as SAT constraints.

   Notice the use of Cards1 to make sure that each tile is used
   exactly once. Remove or change this constraint if a shape can be
   used multiple times, or can even be omitted.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

placement(M, N, Vs, *(Cs) * *(Cards1)) :-
        matrix(M, N, TilesRows),
        pairs_keys_values(TilesRows, Tiles, Rows),
        same_length(Rows, Vs),
        pairs_keys_values(TilesVs0, Tiles, Vs),
        keysort(TilesVs0, TilesVs),
        group_pairs_by_key(TilesVs, Groups),
        pairs_values(Groups, SameTiles),
        maplist(card1, SameTiles, Cards1),
        Rows = [First|_],
        phrase(all_cardinalities(First, Vs, Rows), Cs).

card1(Vs, card([1], Vs)).

all_cardinalities([], _, _) --> [].
all_cardinalities([_|Rest], Vs, Rows0) -->
        { maplist(list_first_rest, Rows0, Fs, Rows),
          pairs_keys_values(Pairs0, Fs, Vs),
          include(key_one, Pairs0, Pairs),
          pairs_values(Pairs, Cs) },
        [card([0,1], Cs)],
        all_cardinalities(Rest, Vs, Rows).

key_one(1-_).

list_first_rest([L|Ls], L, Ls).

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
   We build a matrix M_ij, where each row i describes what placing a
   tile at a specific position looks like: Each cell of the grid
   corresponds to a unique column of the matrix, and the matrix
   entries that are 1 indicate the grid positions that are covered by
   placing one of the tiles at the described position. Therefore,
   placing all tiles corresponds to selecting specific rows of the
   matrix such that, for the selected rows, at most one "1" occurs in
   each column.

   We represent each row of the matrix as Ts-Ls, where Ts is the tile
   that is used in each case.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

matrix(M, N, Ms) :-
        Squares #= M*N,
        length(Ls, Squares),
        findall(Ts-Ls, line(N, Ts, Ls), Ms).

line(N, Ts, Ls) :-
        tile_matrix(Ts),
        length(Ls, Max),
        phrase((zeros(0,P0),tile_(Ts,N,Max,P0,P1),zeros(P1,_)), Ls).

tile_([], _, _, P, P) --> [].
tile_([T|Ts], N, Max, P0, P) -->
        tile_part(T, N, P0, P1),
        { (P1 - 1) mod N >= P0 mod N,
          P2 #= min(P0 + N, Max) },
        zeros(P1, P2),
        tile_(Ts, N, Max, P2, P).

tile_part([], _, P, P) --> [].
tile_part([L|Ls], N, P0, P) --> [L],
        { P1 #= P0 + 1 },
        tile_part(Ls, N, P1, P).

zeros(P, P)  --> [].
zeros(P0, P) --> [0], { P1 #= P0 + 1 }, zeros(P1, P).

下面的查询说明了覆盖哪些网格元素(1)，其中每一行对应于其中一个矩形的位置：

?- M = 7, N = 9, placement(M, N, Vs, Sat), sat(Sat),
  labeling(Vs), matrix(M, N, Ms), pairs_values(Ms, Rows),
  pairs_keys_values(Pairs0, Vs, Rows),
  include(key_one, Pairs0, Pairs1), pairs_values(Pairs1, Covers),
  maplist(writeln, Covers).
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1,1,1,1]
[0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,1,1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
M = 7,
N = 9,
etc.

与解决方案相对应：

​

​

这样的CLP(B)公式通常比CLP(FD)版本的可扩展性更差，这也是因为涉及更多的变量。然而，它也有几个优点：

一个显着的优点是，它很容易推广到任务的一个版本，其中一些或所有形状可以多次使用。例如，在上面的版本中，我们可以简单地将card1/2更改为：

custom_cardinality(Vs, card([0,1,2,3,4,5,6,7], Vs)).

并获得每个瓦片最多可以使用7次的版本，甚至可以完全省略(由于包含了0)。

其次，我们可以很容易地将其转换为精确覆盖问题的解决方案，这意味着每个网格元素都被一个形状覆盖，只需在all_cardinalities//3中将card([0,1], Cs)更改为card([1], Cs)即可。

与其他修改一起，这里是使用四个2x2矩形的4x4栅格的覆盖：

[1,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0]
[0,0,1,1,0,0,1,1,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,1,1,0,0,1,1,0,0]
[0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,1]

CLP(B)公式的第三个优点是可以在不显式枚举解的情况下计算解的数量。例如，对于原始任务：

?- placement(7, 9, Vs, Sat), sat_count(Sat, Count).
Count = 68.

@repeat已经很好地说明了这68个解决方案。

为了进行比较，这里是每个形状可以使用0到7次的解决方案的数量：

?- placement(7, 9, Vs, Sat), time(sat_count(Sat, Count)).
% 157,970,727 inferences, 19.165 CPU in 19.571 seconds
...
Count = 17548478.

在10x10网格上也是如此，计算时间约为6分钟(约20亿个推论)：

?- placement(10, 10, Vs, Sat), sat_count(Sat, Count).
Count = 140547294509.

在11x11网格上，计算约半小时(约90亿个推论)：

?- placement(11, 11, Vs, Sat), sat_count(Sat, Count).
Count = 15339263199580.

最后，也许最重要的是，这种方法适用于任何形状的瓦片，而不限于正方形或矩形。例如，要处理1x1正方形和三角形及其垂直和水平反射，请使用以下tile_matrix/1定义

tile_matrix([[1]]).
tile_matrix(T) :-
        T0 = [[1,1,1,1],
              [1,1,1,0],
              [1,1,0,0],
              [1,0,0,0]],
        (   T = T0
        ;   maplist(reverse, T0, T)
        ;   reverse(T0, T)
        ).

允许这些形状在9x7电路板上使用0到7次，大约一分钟后，我就得到了Count = 58665048314解决方案。

以下是随机挑选的其中一个：

​

​

使用CLP(B)，即使解决方案的数量太多而无法显式地枚举它们，以使每个解决方案的可能性相等的方式选择解决方案也是相当容易的。