Crossword with given grid and words

Question

I have a crossword grid, for example

+-----+
|  *  |
|     |
+-----+

and list of words

a
ababa
bb
cc
ba
bb
ca
cb

Every word must be used. The goal is finding all variants how this crossword can be solved, in this case there are two variants -

bb*cc
ababa

and

cc*bb
ababa

Some more complex crosswords looks like that for example:

+-----+
|   * |
|     |
|    *|
|   * |
|  * *|
|  *  |
|     |
+-----+

with a list of 20 words etc.

I was trying to create algorithm to solve this kind of problem, but without succes. Can someone help me?

Answer 1

First note, that even determining if a crossword is "solveable" using the given dictionary is NP-Hard¹, so even determining if there is 0 or more solution cannot be done polynomially (unless P=NP).

Thus, the alternative is using an exhaustive search solution - just try all possibilities to "place" the words, and then verify if this solution is valid.

Pseudo code:

solve(words,grid):
   if words is empty:
       if grid.isValidSolution():
          print grid as a possible solution
          return
   for each word in words:
       candidate<- grid.fillFirstSpace(word)
       solve(words\{word},candidate)

---

(1) Reference: Is P equal to NP section 3.3