Suppose that I want to enumerate all English language words of length 5. If I've got nothing more than a check of whether an arbitrary string is an English word, I have to do 5^26 calculations. However, suppose that I can check a partial specification to see if there are any words consistent with it. By partial specification I mean an assignment of some letters to some positions, with the others free to vary. E.g. "is there a word that starts with "HO" and ends with "Y" (but has any of the 2^26 configurations of third and fourth letter)?
An obvious algorithm would be to formulate it as a 26-tree, and traverse it depth-first, stopping once a pattern was deemed not "good" (e.g. as far as I'm aware there are no five letter words in English that start with "AAA", so we can skip checking "AAAAA", "AAAAB", ..., "AAAZZ").
Is it possible to do any better (average, worst case)? How about under additional assumptions on the distribution of letters (any such learning would need to be part of the algorithm, since my actual problem is not about natural language)? As another view on the second question: what sorts of heuristics are helpful?