Загадка ECLiPSe CLP: идеальная подгонка прямоугольника

Question

Я работаю над головоломкой, известной как "деление на коробки". По сути, это форма идеальной подгонки прямоугольника, основанная на данных подсказках. Правила таковы:

• Некоторые ячейки сетки содержат числа (это известные входные данные)
• Задача состоит в том, чтобы разделить область сетки на прямоугольные комнаты, удовлетворяющие следующим ограничениям: каждая комната содержит ровно одно число, а общая площадь комнаты равна числу в ней

Например:

4 _ 2
_ _ _
_ 3 _

имеет решение:

+-----------+
| 4  . | 2  |
| .  . | .  |
|------+----+
| .   3  .  |
+-----------+

Я написал ограничения и небольшой решатель конечных доменов, который эффективно дает мне все возможные размещения прямоугольника на подсказку, например, так (координаты начинаются с (1,1) и перемещаются из верхнего левого угла в нижний правый):

% Syntax: rectangle(X,Y,Width,Height,HintValue)
[
  [rectangle(1, 1, 2, 2, 4)],
  [rectangle(2, 1, 2, 1, 2), rectangle(3, 1, 1, 2, 2)],
  [rectangle(1, 3, 3, 1, 3), rectangle(2, 1, 1, 3, 3)]
]

Впоследствии я попытался написать свой собственный решатель, который основан на проверке перекрывающихся ограничений (т. Е. Если два прямоугольника перекрываются по горизонтали, они не должны перекрываться по вертикали и наоборот). Это работает хорошо для маленьких головоломок, однако, ни одна из моих попыток не была успешно расширена до головоломок больше чем ~ 15x15 из-за обширной проверки ограничений.

Таким образом, цель состоит в том, чтобы найти модель, которая будет масштабироваться до более крупных головоломок и, если возможно, таким образом, чтобы можно было использовать встроенный в ECLiPSe поиск /6 и иметь возможность легко экспериментировать с различными эвристиками поиска.

Есть мысли / идеи? Заранее спасибо!

ПРИМЕЧАНИЕ: я работаю с целочисленной библиотекой домена IC (= lib (ic))

(отредактируйте, они теперь все решают менее чем за полсекунды, если кто-то заинтересован в результатах времени выполнения)

Проблема ввода данных:

Синтаксис: проблема (ID, ширина, высота, подсказки) (подсказки - триплетные кортежи: (I,J, значение))

Проблема (р (15,1),15,15,[(9,1,4),(11,1,2),(12,1,3),(14,1,3),(2,2,4),(3,2,2),(4,2,2),(8,2,12),(2,3,3),(10,3,3),(1,4,2),(10,4,11),(15,5,7),(8,7,36),(12,8,24),(3,9,27),(13,9,24),(15,9,7),(4,11,3),(8,11,2),(7,12,6),(8,12,2),(7,13,3),(8,13,2),(10,13,3),(4,14,7),(9,14,3),(10,14,2),(11,14,2),(12,14,6),(6,15,8)]).

Проблема (р (15,2),15,15,[(1,1,9),(11,1,2),(13,1,2),(7,3,36),(13,4,3),(14,4,16),(1,6,2),(7,6,24),(4,7,3),(6,7,8),(2,8,6),(3,8,3),(9,8,7),(7,9,9),(15,9,5),(1,10,5),(3,10,2),(11,10,16),(14,10,5),(1,12,2),(4,12,2),(6,12,3),(10,12,6),(11,12,2),(3,13,3),(7,13,2),(12,13,5),(13,13,7),(1,14,2),(14,14,26),(15,14,2)]).

Проблема (р (20,1),20,20,[(2,1,2),(4,1,2),(11,1,4),(13,1,2),(1,2,2),(5,2,12),(9,2,35),(16,3,15),(19,3,20),(1,4,2),(1,5,2),(4,6,8),(20,6,5),(14,7,2),(3,8,10),(10,8,5),(1,10,4),(5,11,30),(15,13,60),(7,14,24),(12,14,54),(14,14,13),(9,15,54),(1,16,8),(16,18,6),(17,18,3),(19,18,2),(20,18,8),(20,19,3),(18,20,3)]).

Проблема (р (20,2),20,20,[(3,1,3),(6,1,2),(8,1,4),(2,2,2),(4,2,4),(9,2,3),(16,2,15),(17,2,3),(18,2,6),(11,3,2),(19,3,2),(20,3,3),(1,4,4),(5,4,7),(9,4,2),(17,4,7),(19,4,2),(4,5,5),(9,5,2),(10,5,3),(12,5,9),(1,6,2),(2,6,2),(7,6,18),(2,7,2),(10,7,2),(13,7,20),(1,9,20),(20,9,3),(4,10,3),(11,10,45),(15,12,28),(19,12,2),(20,12,2),(5,13,2),(8,13,3),(15,13,40),(6,14,2),(9,14,12),(3,15,14),(5,15,4),(6,15,6),(18,15,18),(3,16,2),(4,16,6),(5,18,3),(14,18,15),(17,18,2),(3,19,2),(5,19,4),(10,19,2),(2,20,6),(5,20,3),(6,20,2),(8,20,3),(16,20,2),(17,20,2),(20,20,6)]).

Проблема (р (25,1),25,25,[(2,1,2),(11,1,10),(15,1,8),(17,1,8),(24,1,2),(13,2,2),(14,2,2),(3,3,6),(12,3,32),(25,3,2),(2,4,2),(4,4,2),(14,4,2),(24,4,8),(25,4,2),(4,5,3),(14,5,4),(13,7,2),(1,8,18),(18,8,56),(21,9,6),(22,9,3),(25,9,4),(2,10,6),(19,10,18),(24,10,4),(10,11,60),(14,11,10),(15,11,4),(23,11,3),(2,12,2),(4,12,5),(10,12,4),(22,12,2),(23,12,3),(24,12,6),(6,13,15),(19,13,2),(21,13,2),(2,14,2),(5,14,28),(17,14,3),(20,14,3),(22,14,2),(18,15,3),(21,15,5),(7,16,7),(12,16,3),(15,16,3),(16,16,2),(9,17,2),(11,17,2),(17,17,3),(20,17,16),(7,18,12),(8,18,2),(9,18,3),(12,18,4),(13,18,9),(19,18,12),(24,18,2),(25,18,3),(1,19,2),(5,19,9),(11,19,2),(3,20,2),(5,20,5),(9,20,2),(20,20,7),(7,21,24),(18,22,6),(20,22,3),(21,22,10),(4,23,6),(5,23,3),(7,23,9),(10,23,12),(16,23,24),(17,23,4),(24,23,5),(1,24,2),(18,24,8),(25,24,2),(2,25,4),(17,25,11)]).

Answer 1

Вы можете сформулировать всю проблему в терминах ограничений конечной области, а затем решить ее с помощью стандартной процедуры поиска. Нет необходимости предварительно вычислять списки размещения отдельных прямоугольников.

Если это домашнее задание, позвольте мне дать несколько рекомендаций. Я бы начал с определения ряда вспомогательных предикатов, таких как

rect_contains_point(rect(I,J,K,L), point(PI,PJ)) :-
    I #=< PI, PI #=< K,
    J #=< PJ, PJ #=< L.

которые пригодятся при формулировании общей модели. Здесь я использовал rect(I,J,K,L) представлять прямоугольник с углами (I,J) а также (K,L), так как это оказывается более удобным для формулировки необходимых ограничений.

Затем вы можете записать условие неперекрытия как

no_overlap(rect(I1,J1,K1,L1), rect(I2,J2,K2,L2)) :-
    K1#<I2 or K2#<I1 or L1#<J2 or L2#<J1.

это тот же метод, который вы найдете в примере на веб-сайте ECLiPSe.

РЕДАКТИРОВАТЬ

Спасибо за предоставление проблемных экземпляров. Я получаю решения для всех из них, а также для сегодняшней головоломки 30x40, менее чем за 1,5 секунды.

Интересно, что вы получаете лучшую производительность с самой наивной стратегией маркировки input_order, Для таких задач с простой геометрической структурой часто лучше всего помечать переменные на основе их "смежности" в геометрии, и просто использование построчного порядка прекрасно работает здесь.

Тем не менее, особенно для задач с дополнительными ограничениями, которые нарушают простую структуру, этот подход может не расширяться в достаточной степени. По этой причине люди разработали специальные ограничения размещения / упаковки, см., Например, disjoint2 в SICStus или nooverlap в Gecode. Последний также доступен в ECLiPSe через disjoint2/1 вlibrary(gfd),

PS

Как сообщает @SeekAndDestroy, стратегия маркировки smallest (выбор переменной с наименьшим на данный момент значением в своей области) дает еще лучшие результаты. Кроме того, используя library(gfd) вместо library(ic) дает дальнейшее ускорение. Я добавил свое решение к примерам на веб-сайте ECLiPSe.