CODEWITHSUNDEEP
prologconstraint-programmingeclipse-clp
SND
SND

Reputation: 1557

ECLiPSe CLP puzzle: perfect rectangle fitting

I'm working on a puzzle known as 'divide-by-box'. In essence, it's a form of perfect rectangle fitting, based on given clues. The rules are:

E.g.:

4 _ 2
_ _ _
_ 3 _

has solution:

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

I have written constraints and a small finite domain solver which efficiently gives me all possible rectangle placements per hint, like so (coordinates start at (1,1) and move from top-left to bottom-right) :

% 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)]
]

I subsequently tried to write my own solver which is based upon checking for overlapping constraints (i.e. if two rectangles overlap horizontally, they should not overlap vertically and vice versa). It works okay for small puzzles, however, neither of my attempts successfully scaled up to puzzles greater than ~ 15x15 because of the extensive constraint checking.

So the goal is to find a model that will scale up to larger puzzles and if possible, in such a way that it is possible to use ECLiPSe's built-in search/6 and be able to easily experiment with different search heuristics.

Any thoughts/ideas? Thanks in advance!

NOTE : I'm working with the integer IC domain library (= lib(ic))

(edit they now all solve in less than half a second in case someone is interested in the running time results)

Problem input data:

Syntax: problem(ID,Width,Height,Hints) (Hints are triplet-tuples: (I,J,Value))

problem(p(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)]).

problem(p(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)]).

problem(p(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)]).

problem(p(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)]).

problem(p(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)]).

Upvotes: 3

Views: 474

Answers (1)

jschimpf
jschimpf

Reputation: 5034

You can formulate the whole problem in terms of finite-domain constraints and then solve it with a standard search routine. There is no need to pre-compute lists of individual rectangle placements.

In case this is homework, let me just give some recommendations. I would start by defining a number of auxiliary predicates like

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

which come in handy in formulating the overall model. Here I've used rect(I,J,K,L) to represent a rectangle with corners (I,J) and (K,L), as this turns out to be more convenient for formulating the necessary constraints.

You can then write the non-overlap condition as

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

which is the same method that you find in the tiling example on the ECLiPSe web site.

EDIT

Thanks for providing the problem instances. I get solutions for all of them, and also for today's 30x40 puzzle, in less than 1.5 seconds.

Interestingly, you get the best performance with the most naive labeling strategy input_order. For such problems with simple geometric structure it is often best to label variables based on their "adjacency" in the geometry, and simply using the row-wise order works fine here.

Still, especially for problems with additional constraints that perturb the simple structure, this approach may not scale up sufficiently. For this reason, people have developed specialised placement/packing constraints, see e.g. disjoint2 in SICStus or nooverlap in Gecode. The latter is also available in ECLiPSe via disjoint2/1 in library(gfd).

PS

As reported by @SeekAndDestroy, the labeling strategy smallest (selecting the variable with the currently smallest value in its domain) gives even better results. Also, using library(gfd) instead of library(ic) gives further speedup. I have added my solution to the examples at the ECLiPSe web site.

Upvotes: 3

Related Questions