Упаковка квадратов в прямоугольник с использованием ограничений (CLINGO)

Question

Используйте CLINGO для упаковки заданного набора квадратов в заданную прямоугольную область без перекрытий. Например, мы хотим упаковать квадраты:

А размера 4, В от размера 3, С & D размера 2, Е размера 1

в зону 5 х 8.

#const x = 8. 
    #const y = 5. 

square(a,4; b,3; c,2; d,2; e,1). 

%generate a grid: 
1 { pos(X,Y) } 1 :- x(X), y(Y). 

%generate placement of the squares 
1 { placement(P, SQ) } 1 :- square(SQ), pos(P). 

%throw out overlaps 

Я не уверен, что ограничение на выброс перекрывающихся квадратов было бы, или если я сделаю это правильно.

Answer 1

Исправить код

Генерация сетки не дает ожидаемых атомов. Вот тот, который вы хотите:

pos (1..x, 1..y).

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

1 {размещение (pos (X, Y), S): pos (X, Y)} 1: - square (S, _).

Теперь мы должны разработать перекрывающиеся ограничения.

Решение проблемы.

Во-первых, мы определяем оккупировать/3, где занимают (S, X, Y) имеет место, когда площадь S занимают сетку в положении (X, Y):

occupy(S,X+I,Y+J):- square(S,Size) ; placement(pos(X,Y),S) ; I=0..Size-1 ; J=0..Size-1. 

Например, square(a,2). placement(a,pos(1,3)). будет связан с occupy(a,1,3).occupy(a,1,4).occupy(a,2,3).occupy(a,2,4)..

Затем отбросить любую модель, которые имеют более чем более чем одной занимают в данной позиции:

:- {occupy(_,X,Y)}>1 ; occupy(_,X,Y). 

Fix: вы должны также отказаться от моделей, где квадрат помещается так занять несуществующее место:

:- occupy(_,X,Y) ; not pos(X,Y).