Algorithm for crossword puzzle with given grid

Question

Before I write something about the problem, I need to let you know:

1. This problem is my homework (I had about 1 week to return working program)
2. I was working on this problem for about a week, every day, trying to figure out my own solution
3. I'm not asking for complete program; I need a general idea about the algorithm

Problem:

Given: a wordlist and a "grid", for example:

grid (X means any letter):

X X 
XXXX
X X
XXXX

wordlist:

ccaa
baca
baaa
bbbb

You have to find example "solution" - is it possible to fit words from wordlist into a given grid? If there is at least one solution, print one (whichever correct). If no - print message, that there is no possible solution. For given example, there is a solution:

b c 
baca
b a 
baaa

It's hard for me to write everything that I've already tried (because English is not my native language and I also have a lot of papers with wrong ideas).

My naive algorithm works something like this:

1. First word needs just proper length, so find any (first?) word with proper length (I'm going to use given example grid and wordlist to demonstrate what I think):

   c X 
   cXXX
   a X
   aXXX
   

2. For first common letter (on the crossing of 2 words) find any (first) word, that fit the grid (so, have proper length and common letter on proper position). If there is no such words, go back to (1) and take another first word. In the orginal example there is no word which starts with "c", so we go back to (1) and select next words (this step repeats few times until we have "bbbb" for 1st word). Now we have:

   b X 
   bXXX
   b X
   bXXX
   

   And we're looking for a word(s) which starts with "b", for example:

   b X 
   baca
   b X
   bXXX
   

3. General process: try to find pairs of words which fit to the given grid. If there is no such words, go back to previous step and use another combination - if there is no such - there is no solution.

Everything above is chaotic, I hope that you understand at least problem description. I wrote a draft of an algorithm, but I'm not sure if that works and how to properly code this (in my case: c++). Moreover, there are cases (even in example above) that we need to find a word that depends on 2 or more other words.

Maybe I just can't see something obvious, maybe I'm too stupid, maybe... Well, I really tried to solve this problem. I don't know English well enough to precisely describe what I think about this problem, so I can't put here all my notes (I tried to describe one idea and it was hard). Believe or not, I've spend many long hours trying to figure out solution and I have almost nothing...

If you can describe a solution, or give a hint how to solve this problem, I would really appreciate this.

Answer 1

The corssword problem is NP-Complete, so your best shot is brute force: just try all possibilities, and stop when a possibility is a valid. Return failure when you exhausted all possible solutions.

reduction that prove that this problem is NP-Complete can be found in this article section 3.3

Brute force solution using backtracking could be: [pseudo code]:

solve(words,grid):
   if words is empty:
       if grid.isValudSol():
          return grid
       else:
          return None
   for each word in words:
       possibleSol <- grid.fillFirst(word)
       ret <- solve(words\{word},possibleSol)
       if (ret != None):
          return ret
   return None

in here we assume fillFirst() is a function that fills the first space which was not already filled [first can actually be any consistent ordering of the empty spaces, but it should be consistent!] , and isValid() is returning a boolean indicating if the given grid is a valid solution.