Creating Dense Boggle® Boards
This page presents an effective simulated annealing method for creating dense Boggle® board layouts.
- General Information and Basic Techniques
- Related Sites
Description of the Boggle® board layout problem
The game of Boggle® involves finding words in a 4x4 or 5x5 grid of letters such that consecutive letters
of the word must be adjacent either vertically, horizontally, or diagonally to each other, and any two positions
in the word may not use the same square of the grid (i.e. no self-overlapping paths). In the following board,
for example,
o---o---o---o---o
| A | T | G | C |
o-|-\---/---\---o
| L | R | J | E |
o---o---o---o---o
| J | R | F | G |
o---o---o---o---o
| M | H | E | S |
o---o---o---o---o
Figure 1: Sample 4x4 Boggle® board containing the word "large".
contains the word "large". In a typical Boggle® game, a player is given a fixed amount of time to discover as
many of these words as possible and at the end of the game receives 1 point for each 3-4 letter word, 2 points
for a 5-letter word, 3 points for a 6-letter word, 5 points for a 7-letter word, 11 points for a 8 (or more)-letter
word. The problem considered here involves constructing a densely populated Boggle® board layout given a
dictionary file containing valid English words (i.e. the highest scoring board possible). For a more complete
description of the game, click here.
Back to the top.
Summary of methods used
The implemented algorithm can be summarized as employing a few basic strategies:
- Start with N random 4x4 board configuration (or 5x5).
- Perturb each of the N random configurations in one of the ways described below. To better determine
perturbation success, the program keeps track of the percentage of times that a particular perturbation
type given a particular parameter succeeds in improving the board configuration. Choice of the
perturbation to be performed on a board is picked randomly among the possible perturbations and parameters
using the weighting based on past performance.
- Change k randomly selected letters on the board.
- Swap k randomly selected adjacent pairs of letters.
- Swap k randomly selected pairs of letters.
- Rotate the board k1 positions vertically and k2 positions horizontally.
- Concatenate the original list of N configurations with the new list of N perturbed configurations, sort
by board score (computed by finding total Boggle® score possible for the board, which is not necessarily
the same as the maximum number of words), and keep the N best configurations. Go to step 2 and repeat.
Back to the top.
Results and relevant files
The code to generate 4x4 Boggle® boards can be found here: boggle.c, and the dictionary
file (the YAWL 0.2 list) can be obtained
here. The best 4x4 Boggle® board layout
I was able to find using this code was:
S E R S
P A T G
L I N E
S E R S
which contains
124 3-letter words ( 124 points)
281 4-letter words ( 281 points)
363 5-letter words ( 726 points)
304 6-letter words ( 912 points)
213 7-letter words (1065 points)
97 8-letter words (1067 points)
28 9-letter words ( 308 points)
4 10-letter words ( 44 points)
4527 total points, 1414 total words.
Figure 2: Best found 4x4 Boggle board configuration.
Click here for the word list.
The best 5x5 Boggle® board layout I was able to find was:
R S C L S
D E I A E
G N T R P
I A E S O
L M I D C
which contains
195 3-letter words ( 195 points)
442 4-letter words ( 442 points)
661 5-letter words (1322 points)
668 6-letter words (2004 points)
533 7-letter words (2665 points)
342 8-letter words (3762 points)
189 9-letter words (2079 points)
71 10-letter words ( 781 points)
18 11-letter words ( 198 points)
1 12-letter words ( 11 points)
13459 total points, 3120 total words
Figure 3: Best found 4x4 Boggle board configuration.
Click here for the word list.
The best 6x6 Boggle® board layout I was able to find was:
D S R O D G
T E M E N S
R A S I T O
D G N T R P
R E I A E S
T S C L P D
which contains
232 3-letter words (232 points)
610 4-letter words (610 points)
907 5-letter words (1814 points)
1087 6-letter words (3261 points)
980 7-letter words (4900 points)
749 8-letter words (8239 points)
429 9-letter words (4719 points)
184 10-letter words (2024 points)
47 11-letter words (517 points)
13 12-letter words (143 points)
5 13-letter words (55 points)
26514 total points, 5243 total words
Figure 4: Best found 6x6 Boggle board configuration.
Click here for the word list.
Back to the top.
Comments to Chuong Do (chuong.do@stanford.edu)