Обработка пролога: пакеты упаковки

Ответ 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)))

(ваш конкретный синтаксис ограничений может отличаться)

Ответ 2

Начиная с версии 3.8.3 SICStus Prolog предлагает ряд специализированных ограничений размещения, которые хорошо соответствуют вашей проблеме с упаковкой. В частности, поскольку проблема с упаковкой является двумерной, вам следует использовать ограничение 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').

Позвольте использовать следующий хакерский запрос для создания изображения для каждого решения размещения над прямоугольниками на доске размером 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 поддерживает ограничение disjoint2/1.

Изменить 2015-04-22

Здесь представлен эскиз альтернативной реализации на основе ограничения tuples_in/2:

• Для каждой пары ящиков определяются все позиции, в которых эти два будут неперекрываться.
• Кодировать действительные комбинации в виде списков кортежей.
• Для каждой пары ящиков следует одно ограничение tuples_in/2.

Как частное доказательство концепции, я реализовал некоторый код, следуя этой идее; как @CapelliC в своем ответе, я получаю отличные решения для ящиков и размеров платы, определенные OP.

Время выполнения сопоставимо с другими ответами на основе CLP (FD); на самом деле она очень конкурентоспособна для небольших досок (10 * 10 и меньше), но становится намного хуже при больших размерах досок.

Пожалуйста, подтвердите, что ради порядочности я воздерживаюсь от публикации кода:)

Ответ 3

Я закодирован в SWI-Prolog

/*  File:    pack_squares.lp
    Author:  Carlo,,,
    Created: Nov 29 2012
    Purpose: http://stackoverflow.com/questions/13623775/prolog-constraint-processing-packing-squares
*/

:- module(pack_squares, [pack_squares/0]).
:- [library(clpfd)].

pack_squares :-
    maplist(square, [5,4,3,2], Squares),
    flatten(Squares, Coords),
    not_overlap(Squares),
    Coords ins 1..10,
    label(Coords),
    maplist(writeln, Squares),
    draw_squares(Squares).

draw_squares(Squares) :-
    forall(between(1, 10, Y),
           (   forall(between(1, 10, X),
              sumpts(X, Y, Squares, 0)),
           nl
           )).

sumpts(_, _, [], S) :- write(S).
sumpts(X, Y, [[X1,Y1, X2,Y2]|Qs], A) :-
    ( ( X >= X1, X =< X2, Y >= Y1, Y =< Y2 )
    ->  B is A+X2-X1+1
    ;   B is A
    ),
    sumpts(X, Y, Qs, B).

square(D, [X1,Y1, X2,Y2]) :-
    X1 + D - 1 #= X2,
    Y1 + D - 1 #= Y2.

not_overlap([_]).
not_overlap([A,B|L]) :-
    not_overlap(A, [B|L]),
    !, not_overlap([B|L]).

not_overlap(_, []).
not_overlap(Q, [R|Rs]) :-
    not_overlap_c(Q, R),
    not_overlap_c(R, Q),
    not_overlap(Q, Rs).

not_overlap_c([X1,Y1, X2,Y2], Q) :-
    not_inside(X1,Y1, Q),
    not_inside(X1,Y2, Q),
    not_inside(X2,Y1, Q),
    not_inside(X2,Y2, Q).

not_inside(X,Y, [X1,Y1, X2,Y2]) :-
    X #< X1 #\/ X #> X2 #\/ Y #< Y1 #\/ Y #> Y2.

Вот последние строки, отображаемые при запуске ?- aggregate_all(count,pack_squares,C)., особенно C подсчитывает общее количество мест размещения

...
0002255555
0002255555
[6,6,10,10]
[7,2,10,5]
[4,3,6,5]
[5,1,6,2]
0000220000
0000224444
0003334444
0003334444
0003334444
0000055555
0000055555
0000055555
0000055555
0000055555
C = 169480.

Ответ 4

Здесь уже есть несколько отличных решений (+1 для всех!), используя ограничения CLP (FD).

Кроме того, я хотел бы показать один концептуально другой способ решения таких задач размещения и покрытия, используя ограничения CLP (B).

Идея состоит в том, чтобы рассмотреть каждое возможное размещение плитки как набора значений TRUE для определенных элементов в сетке, где каждый элемент сетки соответствует одному столбцу матрицы, и каждое возможное размещение плитки соответствует одной строке. Затем задача состоит в том, чтобы выбрать набор строк упомянутой матрицы таким образом, чтобы каждый элемент сетки был покрыт не более одного раза, или, другими словами, в каждом столбце, содержащем не более одного значения 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).

Во-вторых, мы можем легко превратить это в решение для точной проблемы покрытия, а это означает, что каждый элемент сетки покрывается одной из фигур простым изменением card([0,1], Cs) на card([1], Cs) в all_cardinalities//3.

Вместе с другой модификацией, это покрытие для сетки 4x4 с использованием четырех прямоугольников 2x2:

[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.

Эти 68 решений уже красиво проиллюстрированы на @repeat.

Для сравнения здесь приведено число решений, в которых каждая форма может использоваться между 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 минут (~ 2 миллиарда выводов):

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

И на сетке 11x11, рассчитанной примерно через полчаса (~ 9 миллиардов выводов):

?- 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)
        ).

Позволяя каждой из этих форм использовать от 0 до 7 раз на плате 9x7, я получаю через минуту или около того решения Count = 58665048314.

Вот один из них, выбранный случайным образом:

Выбор решений таким образом, чтобы каждый из них был одинаково вероятен, также довольно легко с CLP (B), даже если количество решений слишком велико, чтобы их явное перечисление.