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