1
$\begingroup$

I'm trying to design a new game that requires a 5 x 5 grid of criss-crossed words (like squareword has). I have a word list of about 4600 5-letter words; I think that there are more than 2 x 10^18 ways of choosing 5 words from this list. I have written a brute-force computer program which just chooses 5 random words for the horizontal ones, and then checks to see if the 5 vertical groups also form words. But I've calculated that it would take hundreds of years for the program to check all the possibilities. I must be missing something! The code is below. I know that choosing words randomly won't ever find them all, but that doesn't matter, I just need to find a few working grids. As it is, it finds a partial solution (where the first two vertical groups are real words) about every minute. but after running an hour it still hasn't found a solution with three vertical groups. And I need 5!

while (!found)
            {
                // choose 5 words from the main list
                for (w = 0; w < 5; w++)
                {
                    horiz[w] = words[rnd.Next(num)];
                }
                // find the newly-formed vertical 'words'
                for (w = 0; w < 5; w++)
                {
                    vert[w] = horiz[0][w].ToString() + horiz[1][w].ToString() + horiz[2][w].ToString() + horiz[3][w].ToString() + horiz[4][w].ToString();
                    // lookup to see if the vertical 'word' is real word
                    if (words.Contains(vert[w]) == false) break;
                }
  
                if (w > 1) { 
                    Console.WriteLine("found partial solution, " + w + ":");
                    Console.WriteLine(horiz[0]);
                    Console.WriteLine(horiz[1]);
                    Console.WriteLine(horiz[2]);
                    Console.WriteLine(horiz[3]);
                    Console.WriteLine(horiz[4]);
                }
                if (w == 5)
                {
                    Console.WriteLine("found solution!");
                    found = true;
                }
                ++tries;
            }
        }
$\endgroup$
3
  • 2
    $\begingroup$ A way to reduce such a search space is to index your dataset. For instance, five indices giving lists of words with a particular letter in a particular position would be useful. Then instead of searching brute force, you could just loop over the words with a match in that position. $\endgroup$
    – Hack Saw
    Feb 1 at 0:10
  • $\begingroup$ Are you primarily looking for ways to optimize your code? Is that the question? $\endgroup$
    – bobble
    Feb 1 at 0:14
  • $\begingroup$ I'm looking for a different algorithm; optimising my existing code isn't going to get anywhere near fast enough. @gareth in his answer below has some good ideas to try $\endgroup$
    – quilkin
    Feb 1 at 9:11

2 Answers 2

3
$\begingroup$

The classical data structure for looking up words as you go, for example as you type, is the Trie, a tree where the links from a parent to a child are the letters and where the path through the tree (plus an end marker) defines a word. You can build such a trie with your pool of words and then create your empty grid of letters. Now create iterators, that is pointers that walk your tree, for each row and for each column of your grid:

         c0 c1 c2 c3 c4
          ↓  ↓  ↓  ↓  ↓
    r0 → [] [] [] [] []
    r1 → [] [] [] [] []
    r2 → [] [] [] [] []
    r3 → [] [] [] [] []
    r3 → [] [] [] [] []

When you begin your search, all r and c iterators start at the root node of your tree. Now try all cells of your grid recursively in the usual reading order. When you cannot make a word at a certain cell, stop.

The row and column iterators will tell you immediately, which common letters you can use to go on, because they are already at the correct place in the respective words. Advance these iterators as you fill in more of your geid.

This technique will find about 45,000 squares with unique five-letter words from a pool of about 4,400 words in about half a minute.

This creates a lot of valid squares, but you need only a few. The algorithm finds its first hit early, so you can stop then. The problem is, it will always result in the same square. We can randomize the results by testing the letters in a different order in every cell. Insead of using ABCDE... in all cells, let's use FOWBM... in the first cell, XGTOQ... in the second and so on. We can do that by creating a set of auxiliary order arrays and shuffle them at the beginning.

Here's some C code that does that.

$\endgroup$
4
  • $\begingroup$ Excellent, thankyou. 10 seconds to find a working grid. I only need one grid per day. Two hours to teach vscode how to compile C (not C++)! This will be running on a .NET server so I will need to rewrite in c# $\endgroup$
    – quilkin
    Feb 1 at 16:25
  • 1
    $\begingroup$ Hehe, sorry about that. I thought that C code was inocent enough that you could compile it with C++, but C++ wants explicit type casts instead of implicit type conversions in four places. The code shouldn't be too hard to port to C#, I think: you'll want to make Trie and Grid classes with proper constructors and the trie_* and grid_* functions as methods. $\endgroup$
    – M Oehm
    Feb 1 at 16:52
  • $\begingroup$ Started on the c# conversion but got stuck with converting double pointers to arrays, But that's getting off-topic. I love your word list, with words getting progressively less common. May I ask where it originates? $\endgroup$
    – quilkin
    Feb 1 at 21:51
  • $\begingroup$ It's from SCOWL, where words are grouped by dialect, by occurrence and vaguely thematically. Each group is in its own file, so you can concatenate a list according to your needs. $\endgroup$
    – M Oehm
    Feb 2 at 5:21
6
$\begingroup$

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 :-).

$\endgroup$
4
  • $\begingroup$ Some good ideas there, thank you. To save me some time, any chance of posting your Python code? I've also realised that maybe I shouldn't be using C# Strings but fixed-length char arrays instead. $\endgroup$
    – quilkin
    Feb 1 at 9:13
  • 1
    $\begingroup$ I just typed it in at the REPL in a terminal window which I've since closed, so I don't have it readily available for posting. Shouldn't take long to reconstruct, though. [EDITED to add:] Oh, you're in luck, either my terminal program or jupyter console remembered it. [EDITED again to add:] Done now. $\endgroup$
    – Gareth McCaughan
    Feb 1 at 21:49
  • $\begingroup$ Thanks for that, although in the interim I have used Martin's 'c' code and marked it as my answer. Your explanation is more detailed though. $\endgroup$
    – quilkin
    Feb 2 at 10:06
  • $\begingroup$ Fine either way. His is surely much more efficient than mine. $\endgroup$
    – Gareth McCaughan
    Feb 2 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.