1
$\begingroup$

I'd like some help in understanding and setting up (what may be) an optimization problem that has some similarities to the 0/1 knapsack problem. In this problem the items are a given number of words (analogous to knapsack items) that can go into the given fields of a crossword puzzle (analogous to a knapsack). A word can fit into a field if their lengths match. The constraints are, as usual, that the letters where any two fields intersect must be the same letter. The goal is to fill the fields with as many words as possible from the given set of words. In general, some fields may ultimately be left unfilled--eg, if there are no words remaining that meet all intersecting field constraints.

At first I thought this could be approached as an optimization problem like the 0/1 knapsack. The initial fields might be filled longest first (analogous to an efficient knapsack solution). But the progressive selection of words is not filling an undifferentiated space like a knapsack. Rather each next selected word must exactly fit into one of the remaining fields. I can't tell if this lends itself to an optimization algorithm, or requires falling back to brute search through all possibilities. What could be a good objective function to maximize? Maximizing the number of filled fields or the number of selected words is a possibility, but can this kind of optimization be used to kill a lot of nodes in the search tree like it does for the knapsack problem?

I can solve the standard knapsack problem with a branch & bound algorithm that relaxes the item weights when progressively filling, but not sure if something like this would work for this crossword problem.

PS: For those who haven't studied the 0/1 knapsack, here is a short video that (purports) to explain some of the key considerations https://www.youtube.com/watch?v=yV1d-b_NeK8

Edit: Here's an example problem, with the best solution (as suggested by A.Omidi):

Wordset = (squid sound swiss pique roses best suns weds psst nod ssw)

Fieldset = (1across 5across 6across 7across 8across 1down 2down 3down 4down 6down)

@PSST
@IOW
SQUID
SUNS@
WEDS@

Best solution found by brute force search through all possibe field/word pairs:

<FILL (6DOWN SSW) NIL 6.0 8 0.0
  ((FILLED 1ACROSS) (FILLED 1DOWN) (FILLED 2DOWN) (FILLED 3DOWN) (FILLED 6ACROSS) (FILLED 6DOWN) (FILLED 7ACROSS) (FILLED 8ACROSS)
   (REMAINING-FIELDS&WORDS-HT #<HASH-TABLE :TEST EQUAL :COUNT 2 {258ED8D1}>) (TEXT 1ACROSS "PSST") (TEXT 1DOWN "PIQUE")
   (TEXT 2DOWN "SOUND") (TEXT 3DOWN "SWISS") (TEXT 4DOWN "T?D") (TEXT 5ACROSS "IOW?") (TEXT 6ACROSS "SQUID") (TEXT 6DOWN "SSW")
   (TEXT 7ACROSS "SUNS") (TEXT 8ACROSS "WEDS") (USED-FIELD-IDS-HT #<HASH-TABLE :TEST EQ :COUNT 8 {258ED3E9}>))
  NIL>

My main question is whether choosing an appropriate objective function (eg, maximizing the number of words filled in) will actually prune the search tree. My intuition is that, contrary to knapsack pruning, it will not significantly prune the tree. (But I haven't programmed it; fair amount of work just to test.)

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Would it be possible to show the problem with a simple example? $\endgroup$
    – A.Omidi
    Mar 27 at 9:37
  • 1
    $\begingroup$ Your example output seems to be saying that it filled 6 down when there is no 6 down field (field set stops at 4 down), and says 5 across contains "IOW" but 1 down contains "PIQUE" (which would seem to place an "E" at the start of 5 across). This is confusing. $\endgroup$
    – prubin ♦
    Mar 28 at 3:09
  • $\begingroup$ You're right, I messed up and forgot about 6down. Also added some other words to make the problem search more realistic. $\endgroup$
    – davypough
    Mar 28 at 4:40

1 Answer 1

Reset to default
1
$\begingroup$

You can certainly model this as a binary integer program. The constraints are very straightforward, and either filling the maximum number of fields or (equivalently) maximizing the number of words used makes sense to me. Whether it would solve efficiently is an empirical question.

It could also be modeled as a constraint programming problem. The number of variables would be smaller. Where an IP model would use a binary variable $x_{i,j}$ to indicate whether word $i$ gets stuffed into field $j,$ a CP model might use an integer variable $y_j$ with domain $0,\dots,W$ (where $W$ is the number of words) to select the word that goes into field $j$ (with $y_j=0$ indicating the field is left empty). Alternatively, you might use a variable $z_i$ with domain $0,\dots,F$ ($F$ the number of fields) to indicate the field into which word $i$ gets stuffed (again using $z_i=0$ to indicate the word is unused). In fact, you might very well include both sets of variables, together with compatibility constraints (word $i$ going into field $j$ implies word $k$ cannot go into field $\ell$ because the fields intersect in what would be different letters for the two words). A CP approach avoids a bunch of matrix arithmetic and does domain reductions more directly (if I put word $i$ in field $j,$ then it cannot be used anywhere else and these other words no longer can be used in these intersecting fields).

In my very limited experience with CP, one drawback relative to IP models tends to be weaker objective bounding with CP. I'm not sure that would be a big issue with this particular problem.

Improve this answer
$\endgroup$
8
  • $\begingroup$ I'm not experienced with CP either, but I'm wondering if it offers the same capability for pruning that state-space search does (eg, in using a relaxation or bounding function for pruning infeasible nodes). There is constraint propagation in CP, but not sure how this would work for this problem. I'm also wondering if maximizing the number of filled squares (instead of filled fields) might offer more resolution for a bounding function to work with in killing unproductive states. Any comments? (ps: Some kind of bounding is required for this kind of problem, because the state space is huge.) $\endgroup$
    – davypough
    Mar 27 at 18:56
  • $\begingroup$ Maximizing filled squares would make the model larger. You would need a variable for each square, indicating whether it was filled or not, along with associated constraints. This is due to the intersection squares. If the fields did not intersect, maximizing filled squares would be maximizing the weighted sum of fields used (weight = length of field). $\endgroup$
    – prubin ♦
    Mar 27 at 19:24
  • $\begingroup$ In your problem, the only "infeasible" nodes will be nodes that cannot improve on the current incumbent objective value. If the objective is to maximize the number of fields filled, then whenever domain propagation after a branch eliminates the last possible entry for a field, the bound for the current subtree will update and maybe result in pruning. If you are branching on whether or not word a goes in field b, the "no" child will at best move the bound by 1 (if a was the last possible entry for b). ... $\endgroup$
    – prubin ♦
    Mar 27 at 19:34
  • $\begingroup$ ... The "yes" child may potentially move the bound by more than 1 (if putting a in b blocks the last remaining candidates for two or more intersecting fields). Also, keep in mind that domain propagation in a CP model may be faster (execution time per branch) than pivoting and adding cuts in an IP model. Bottom line: it's an empirical question. $\endgroup$
    – prubin ♦
    Mar 27 at 19:34
  • $\begingroup$ Glad to get some deeper insights from our discussion. Re using the # of filled squares as a bounding function (instead of filled fields): This shouldn't be an issue, since all field lengths are fixed, and it's easy to maintain a running total of filled squares as each field is filled. If an intersecting field also happens to get filled (ie, last letter), its length would be added in at the same time. $\endgroup$
    – davypough
    Mar 28 at 2:17

Your Answer

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.