Is there some feasible (i.e. polynomial time) algorithm which builds, starting from a small (~20) set of words, a crossword which maximizes (or at least for which is "big") the number of intersection? Or, if the intersection criteria is impractical, is it possible to maximize the density (in some sense) of the crossword?
I have already written an exhaustive search in Python, but it takes too long for more than six words...
See also: Algorithm to generate a crossword (but the answers there, althought good, do not really tackle my issue).
Is there some polynomial time algorithm ?
Answer: No.
For a simple version: if a word end's letter is the same of another word beginning's, we can concatenate them. for example:
cat+tree+element -> Valid
aaa+aaa -> Valid
cab+aboard -> Invalid ('a' != 'b')
Question is: try to concatenate words as many as possible.
But it's equivalent to Hamiltonian path problem, so we don't have any polynomial time algorithm for this problem.
See this for details: Hamiltonian path problem
PS:
For a small (~20) set, you can try heuristic search or Dynamic programming method to get a feasible solution.