Technique 0: Use well chosen data structures.
I am guessing from your use of the word "list" that the thing called words in your code is something like an ArrayList. Note that calling Contains on this requires a search through all elements of the list, which is pretty slow. Consider using something that has a more efficient Contains method.
(Maybe you're already doing that; I can't tell since the code you've posted doesn't show how words is created.)
Technique 1: Rule things out faster.
For instance, I just wrote a simple-minded thing in Python (which is likely much slower than the C# you're using, though maybe almost all the time is spent in data-structure lookup operations that are efficiently implemented inside the Python runtime) that works as follows:
- For each length from 2 to 4, construct a set object (implemented internally as some sort of tree or hash table or the like; membership tests should be fairly efficient) containing all prefixes of words of that length.
- Now: for each choice of first + second row, check whether all the 2-letter column prefixes are possible, and bail early if not; for each of these, try all third rows, and again check for each whether all 3-letter column prefixes are possible and bail early if not; ditto for fourth row; finally try fifth-row possibilities and check each against the full set of words.
This has found hundreds of full 5x5 squares in the time I've spent writing this comment. (Using a word-list with about 6000 words in it, so it's an easier business than with your slightly smaller list. Probably not more than 10x easier, though.)
Technique 2: Only explore available bits of the tree.
If the code mentioned above had been too slow (which it would be if you needed it to run quickly every time someone wants to play a game), the next thing I would have tried (a little more work, but not much more) would be something like this:
- For each length from 1 to 4, construct not just a set of legal prefixes but a mapping from the prefix to the set of all words with that prefix.
- For each first row, enumerate possible first columns beginning with the correct first letter.
- For each (first row, first column), enumerate possible second rows beginning with the correct first letter, and bail early when impossible as above.
- For each (first two rows, first column), enumerate possible second columns beginning with the correct first two letters, and bail early when impossible as above.
- For each (first two rows, first two columns), enumerate possible third rows.
- Etc.
(It's not completely clear whether the bail-early logic gains enough to justify its cost here, but my guess is that it does.)
My code just iterates sequentially over the word list at each relevant point, but of course you could sample randomly from it instead provided you've got an efficient way of picking random elements from whatever collection object you're using. (You might find that you need to construct one thing for testing membership and another for choosing random elements, if the C#-or-whatever standard library doesn't offer a collection type that does both efficiently. That's probably fine -- you only need to build these things once.)
[EDITED to add:] The approach described under "Technique 2" is quite closely related to M Oehm's suggestion to use a trie; the "prefix -> possible successors" thing is basically a trie implemented simply but inefficiently on top of data structures that Python happens to make easily available.
Here's my crappy code using technique 1 but not technique 2:
w5 = set(w for w in open("path/to/wordlist.txt").read().lower().split() if len(w)==5)
prefixes = [set(w[:k] for w in w5) for k in range(5)]
n=0
nn=1
for a in w5:
for b in w5:
if not all(p+q in prefixes[2] for (p,q) in zip(a,b)): continue
for c in w5:
if not all(p+q+r in prefixes[3] for (p,q,r) in zip(a,b,c)): continue
for d in w5:
if not all(p+q+r+s in prefixes[4] for (p,q,r,s) in zip(a,b,c,d)): continue
for e in w5:
if not all(p+q+r+s+t in w5 for (p,q,r,s,t) in zip(a,b,c,d,e)): continue
n += 1
if n >= nn:
print(nn)
nn *= 4
Obviously all the stuff with n and nn is just giving me some idea of how much progress it's making. And, for the avoidance of doubt, this is really ugly code and you should aim to do better :-).
