How to generate board for game like boggle

Question

There are many Boggle like games on Google Play, Apple Store and Facebook platform. How do I generate a playable board like those games?

Answer 1

the simplest way is to generate a grid of random characters selected uniformly. but that will not give you many words:

from random import randint

N = 4

def display(letters):
    for row in letters:
        print('+%s+' % '+'.join('-' * N))
        print('|%s|' % '|'.join(row))
    print('+%s+' % '+'.join('-' * N))

def uniform_char():
    return chr(ord('A') + randint(0, 25))

def to_array(fn):
    return [[fn() for _ in range(N)] for _ in range(N)]

display(to_array(uniform_char))

giving

+-+-+-+-+
|B|G|C|Z|
+-+-+-+-+
|G|B|T|K|
+-+-+-+-+
|I|R|O|Q|
+-+-+-+-+
|G|A|S|W|
+-+-+-+-+

an improvement on that would be to weight letters by how often then occur in english (assuming that is the language you want):

from collections import Counter

def letters():
    with open('/usr/share/dict/words', 'r') as words:
        for word in words:
            for letter in word.upper():
                if letter >= 'A' and letter <= 'Z':
                    yield letter

letter_scores = Counter(letters())
print(letter_scores)

# http://stackoverflow.com/questions/14992521/python-weighted-random/14992648
def weighted_random(pairs):
    total = sum(pair[1] for pair in pairs)
    r = randint(1, total)
    for (value, weight) in pairs:
        r -= weight
        if r <= 0: return value

display(to_array(lambda: weighted_random(letter_scores.items())))

giving

Counter({'E': 301968, 'S': 274630, 'I': 241084, 'A': 225091, 'R': 191386,
'N': 191320, 'O': 184143, 'T': 177237, 'L': 151341, 'C': 111066, 
'U': 90838, 'D': 89014, 'M': 80645, 'P': 79507, 'G': 71689, 'H': 71423, 
'B': 52921, 'Y': 47941, 'F': 32114, 'V': 27918, 'K': 26797, 'W': 22635,  
'Z': 14022, 'X': 7861, 'J': 5130, 'Q': 4722})

+-+-+-+-+
|L|E|S|T|
+-+-+-+-+
|O|A|C|P|
+-+-+-+-+
|A|I|L|L|
+-+-+-+-+
|N|G|S|I|
+-+-+-+-+

better still would be to use n-grams (eg common letter pairs) and a markov chain or just some kind of random sampling. here i start with letters weighted by probability (as above) and then set a few neighbours to popular pairs (in mix i choose a random point, find a letter that commonly follows the letter there, and set a neighbouring square to that):

def pairs():
    with open('/usr/share/dict/words', 'r') as words:
        for word in words:
            prev = None
            for letter in word.upper():
                if letter >= 'A' and letter <= 'Z':
                    if prev: yield (prev, letter)
                    prev = letter

pair_scores = Counter(pairs())
#print(pair_scores)                                                             
start = to_array(lambda: weighted_random(letter_scores.items()))

def mix(array):
    x, y = randint(0, N-1), randint(0, N-1)
    a = array[y][x]
    neighbours = [(pair[1], score)
                  for (pair, score) in pair_scores.items()
                  if pair[0] == a]
    if neighbours:
        b = weighted_random(neighbours)
        # print(a, b, neighbours)                                               
        array[(y+randint(-1,1))%N][(x+randint(-1,1))%N] = b
    else:
        print('no neighbours for', a)

for _ in range(N*(N-1)//2): mix(start)
display(start)

giving

+-+-+-+-+
|L|T|H|P|
+-+-+-+-+
|S|S|S|O|
+-+-+-+-+
|S|O|O|L|
+-+-+-+-+
|E|S|A|E|
+-+-+-+-+

not sure it's a big improvement, but note double S, TH, etc.

finally, of course, you could just note the letters on the dice used in boggle and select from each of those at random, exactly emulating the game.

all code python 3 on linux.

Answer 2

You can google for "Boggle letter distribution" on dices. Distribution is different for 4x4 and for 5x5 board. And there are also variations for same size boards. Some of them are given on Wikipedia's Boggle talk page (which is not of permanent nature, so grab them now). Note that letter Q counts as two letters, QU, but is written as a single letter in distribution sheets.