# Creating Dense Boggle® Boards

This page presents an effective simulated annealing method for creating dense Boggle® board layouts.

## 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:
2. 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.
1. Change k randomly selected letters on the board.
2. Swap k randomly selected adjacent pairs of letters.
3. Swap k randomly selected pairs of letters.
4. Rotate the board k1 positions vertically and k2 positions horizontally.
3. 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.```