How to create letter grids with a lot of words

Question

The question is mainly "how to create a grid of good for the game" Boggle "with a lot of words" where good is defined as containing many words of 5 or more letters.

Boggle - a game in which you roll dice with letters on them, they are placed in a 4x4 grid. Example:

HSAV ENIS KRGI SOLA 

Words can be made by joining letters horizontally, vertically or diagonally. In the above table you can make good words "VANISHERS", "VANISHER", "KNAVISH", "ALIGNERS", "SAVINGS", "SINKERS" and about 271 other words depending on the dictionary are used, for example, "AS", " I "," AIR "," SIN "," IS ", etc.

Like a bad example of this grid

 OVWC TKZO YNJH DEIE 

has only ~ 44 words, of which only 2 letters are> 4 letters long. "TYNED" and "HINKY".

There are many similar questions , but AFAICT is not this exact question. This is, of course, a link to Scramble with Friends.

The first solution, collecting letters at random, has a problem: if you accidentally chose all the consonants, there will be no words. Adding a few random vowels is not enough to guarantee a good set of words. You can only get from 1 to 4 alphabetic words, while a good algorithm will choose a set of letters that contain> 200 words with many words> 7 letters.

I am open to any algorithm. Obviously, I could write code to solve brute force by finding all possible grids, and then sort them by grids using most words, but this simple solution will start forever.

I can imagine various heuristics, for example, choosing a long word (8-16 letters), placing these letters in a grid at random, but in such a way that it can actually make a word and then fill the left spaces. I suspect this is not enough to guarantee a good set of words, although I have not tried it yet.

Perhaps the solution requires pre-processing the dictionary in order to know the common parts of the words. For example, all words that end with the words "ing" or "ers" or "ght" or "tion" or "land". Or somehow arrange them in a graph of common letters. Maybe weighing certain sets of letters, so "ing" or "ers" are often inserted.

Ideas?

Answer 1

With the exception of the brute force search suggestion, there is probably no way to guarantee that you have a good grid. If you use the letter frequency found on the Boggle bone, you will get “medium” grids (just like you would roll the dice). You can improve this by adding additional heuristics or filters, for example:

  ensure that (almost) every consonant is 'in-reach-of' a vowel ensure 'Q' is 'in-reach-of' a 'U' ensure the ratio of vowels to consonants is within a set range ensure the number of rare consonants is not too large etc 

Then you could

  set letters using weighted letter frequency change (swap/replace) letters not meeting your heuristics 

It is still possible that the bad grid will go away if you do not check with brute force, but you can significantly reduce the number of bad grids compared to those returned by a simple randomly generated grid.

Alternatively, generate random grids and do the rough work required to select good grids. But do it in the background (a few days or weeks before). Then store a bunch of good grids and randomly select as needed (and cross them out so you don't see it again).

Answer 2

The way Boggle works is that there is a hexagonal matrix with certain letters on the side. These dies are randomly assigned to 16 squares and then rolled up. Regular letters are found on a larger number of cubes. Search around - you can get the exact set of cubes.

Answer 3

• Calculate the frequency of the frequency and frequency of letter letters from the dictionary.

• Start by randomly selecting one of the four center squares.

• Randomly select a letter for this square, weighted by one letter frequency.

• Recursive:

  4.1. Randomly select one of all empty connected squares.

  4.2. Randomly select a letter for this square, weighted by a combination (on average) of the two-frequency frequencies of any connected filled square and the single-letter frequencies of any connected empty square.

Et voila!

PS You might also want to experiment with adding deflation in a global letter, based on his current count of appearances in the grid up to 4.2.