Depth first search or backtrack recursion for finding all possible combination of letters in a crossword puzzle/boggle board?

Question

What would be the time complexity? I just want to avoid this being O(n!). Would using depth first search be time complexity O(n^2), as for each letter it may have to go through all other letters worst case?

I guess I'm not sure if I'm thinking about this the right way.

When I say use depth first search, I mean starting depth first search from first the letter, and then starting from the second letter, etc.

Is that necessary?

Note:
The original problem is to find all possible words in a crossword/boggle board. I'm thinking of using the trie data structure to find if a word is in the dictionary, but am thinking about ways of generating the words themselves.

Answer 1

Following the discussion above, here is my answer:

Definition: a trieX is a sub trie, with words of length X only.

Since we have a trie with all words in the desired language, we can also get the appropriate trieX.

We say that the crossword puzzle has w words, so we create an array w long where each entry is the root of a trieX where X is the length of the relevantword. This gives us the list of possible words in each blank word.

Then the iterate over intersections between words and eliminate words that can not be placed. When there are no more changes done - we stop.

Two remarks:
1. In order to improve performance, we start by adding either long words, or VERY short ones. What is short or long? have a look at this and this.
2. Elimination of words from the trieX's can also be done by checking dependencies between words (if THIS words is here, then THAT words can't be there, etc.). This is more complicated, so if anyone wants to add some ideas on how to do this easily - please do.