3

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:

  • Some grid cells contain numbers (this is known input data)
  • The task is to partition the grid area into rectangular rooms satisfying following constraints: each room contains exactly one number and the total area of the room is equal to the number in it

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

1 Answer 1

3

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.

4
  • Thank you for your comment. It's actually quite an honour to receive an answer from you, since I've read and got inspired by several of your works. Eclipse clp is truly an amazing system! On-topic: I've just implemented the model approach you suggested in which I don't pre-compute possible rectangles and work with corner coordinates and it is a really succesfull improvement given the much simpler overlapping constraints. This implementation can efficiently handle most 15x15 puzzles and even various 20x20 puzzles, however it's still not scalable enough. I will edit my post with the results.
    – SND
    Mar 18, 2016 at 10:58
  • Thanks for the kind words, and the puzzle instances. I have amended my answer.
    – jschimpf
    Mar 18, 2016 at 14:48
  • It appears -for my code- if I change the selection method from input_order to smallest, all puzzles are solved within less than half a second using the new model. Thanks again!
    – SND
    Mar 22, 2016 at 12:31
  • Hmm, I could swear I tried that and it was slower... But you are right, and it makes sense. Anyway, I added a link to my final code, which includes this improvement.
    – jschimpf
    Mar 22, 2016 at 13:53

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.