The basic structure of the program is depth-first search.  Most of the
optimizations are to make sure it always considers the most
constrained incomplete word next. For instance, if a partially filled
in puzzle looks like this,

  ????
  ????
  ZONE

the program tries to fill in the word ending in Z before the word
ending in E: there are 69 three letter words that end in E, but only 9
that end in Z.

The other big deal is to avoid searching the whole word list. Whenever
the program fills in a word, it re-computes the list of all words that
fit in the words that cross that word. For instance, when it added
ZONE, it attached the list of all three-letter words ending in Z to 1
down. This really speeds up subsequent consideration of the
cross-words.

My program has at least one glaring flaw: it can get into infinite
loops.  Mostly it does depth-first search, which never loops. But
sometimes it decides to re-order the layers of the search so that it's
always working on the most constrained word. This re-ordering loses
the state required to avoid re-considering partial solutions that the
program has already tried.

If you have really extravagant resources available, some other
optimizations are available. For a while I tried to use the huge
memory on a CM-2 Connection Machine as a hash table to speed the
decision about whether adding a word would still allow all the
cross-words to be filled in. The entries in the hash table were all
possible partial words: QU?? was in it, but QZ?? was not. I never
finished this project, but it might be worth pursuing.