I’m trying to create a word game, just like WORDAMENT, in my spare time. In order to present a new round, I need to create a board with 16 letters organized in a 4*4 grid. Currently, I’m generating the grid randomly. But it has some obvious problems. So my main purpose is to organize those 16 letters in such a way that maximum number of words can be formed out of connected tiles. How shall the letters be organized ? I think this comes down to the probability of occurrence of letters in the English language. How can I use the letter frequency table, to organize my tiles? Any relevant pointers/suggestions/articles are appreciated. Thanks.
4
Sometimes, it is simpler to “cheat” a little bit and start from the answer. In this case, I am more likely to take a set of words and continue to arrange them on board in the remaining spots until some criteria is met, and then fill the rest randomly.
For example, I’ll pick a dictionary with the relatively “simple” words and create my word DB so that I can efficiently look up a random word based on two criteria: 1) How many letters do I want in a word, and 2) Which letter should the word begin with.
This is how I would build the game:
1) Pick a word from dictionary that’s either 6 or 7 chars long. Put it on the board in a random order. Let’s say the word was BORDER:
2) Find 2-3 consecutive empty spaces. Pick an adjoining letter and find a word from the dictionary that can meet the length (i.e. based on empty spaces) and begins with that letter. Arrange the letters on board. For example, after DINE is added:
3) Again, this time around BET:
4) Iterate until you can no longer find 2 consecutive empty spaces. Fill any single spaces with random characters. So after adding NUN and ZOO, the last space is filled with P:
Done. Now if you look at the final board, since the algorithm had especially added a few words, they are bound to be there. Since they were English words, they are likely to make a lot of combinations with other words since they are arranged together on the board. So you can easily see a few words already that were never initially added: ODE, BOO, RIDE, BODE, PEN, RUN, PRIDE, etc. I am sure if you play more with this board, you’ll find many more 🙂
I would play with the variables (e.g. is 6-7 letter the best way to start, or larger or smaller), and how to decrease the length (i.e. if 5 consecutive blocks are available, should add a word for 5 letters, or two smaller ones, etc.).
There are two things you need to do: (1) start with plausible heuristics (2) test the generated grid.
Some plausible heuristics would include (for example):
- Match frequency of letters in English: ETAOIN SHRDLU etc etc. See here.
- Maintain vowel balance (about 40%).
- No more than 1 or 2 rare letters (ZJQX) and no Q without U.
- Other heuristics related to the specific rules of the game, such as centre/edge or adjacencies.
Then test solve the grid. Write a program to count the words using a suitable dictionary (it’s not that hard) and rate the grid according to the score you get: Novice, Regular, Expert, Impossible.
This kind of strategy applies to lots of games, not just this one.
Test solving also:
1. Lets you discard grids that are just too hard, or easy, or have too many or too few short or long words.
1. Lets players choose according to the level of difficulty they prefer.
1. Could allow you to tweak a grid by moving or swapping letters to achieve a result.
None of these things can be achieved by heuristics.
2