What is a sensible algorithm to generate the letters in Letterpress iOS game?

Question

I've been playing Letterpress a lot lately.

The aim of the game is pretty much to score as many blue tiles as possible by making words out of the letters on the board. When you play your word, letters composing the word will turn blue unless the letter was surrounded by red tiles.

A regular Letterpress board looks like this:

I realised that the letters on the board must be generated with some sort of rules, otherwise it will be really hard to play the game with some boards. I could only think of the rule where there must be a number of vowels. I wonder if there are other rules in place.

Additionally, I wonder if this will be anything similar to generating Boggle dices.

Answer 1

I decided to hack together a solution based on user166390's suggestion. The frequencies you see are for the English language, taken from Wikipedia. Running the program a few times and just eyeballing the results, they look pretty playable to me. I can generally find a few four- or five-letter words at least, and I'm not even very good at the game! Anyway, here's the code:

#!/usr/bin/env python

from random import random
from bisect import bisect_left

letters = [c for c in "abcdefghijklmnopqrstuvwxyz"]
frequencies = [8.167, 1.492, 2.782, 4.253, 12.702, 2.228, 2.015, 6.094, 6.966,
               0.153, 0.772, 4.025, 2.406, 6.749, 7.507, 1.929, 0.095, 5.987,
               6.327, 9.056, 2.758, 0.978, 2.360, 0.150, 1.974, 0.074]

cumulative_frequencies = [sum(frequencies[0:i+1]) for i in xrange(len(frequencies))]

for i in xrange(5):
    line = ""
    for j in xrange(5):
        line += letters[bisect_left(cumulative_frequencies, random() * cumulative_frequencies[-1])] + " "
    print line

The idea is, for each letter to be generated, use the roulette wheel algorithm to choose it randomly with probability proportional to the frequencies given.

Answer 2

I've heard Loren Brichter, the dev, talk about it, bit I can't for the life of remember where. I think it was on Guy Ritchie's Debug podcast, but I'm not sure. I remember a few things.

He guarantees at least a certain number of vowels.

The consonants are generated separately from the vowels. This implies separate letter distributions.

He did his own analysis of the dictionary behind the game to come up with the letter distribution.

If a Q is chosen an I is guaranteed so a word is always possible with the Q.

I play a lot. I have never had a game end for any reason but all letters being used. I don't know if it's guaranteed a word is always possible with every letter, but it sure seems it's practically true even if not enforced.