I think you will probably spend most of your time trying to match words that can't possibly be built by your letter grid. So, the first thing I would do is try to speed up that step and that should get you most of the way there.
For this, I would re-express the grid as a table of possible "moves" that you index by the letter-transition you are looking at.
Start by assigning each letter a number from your entire alphabet (A=0, B=1, C=2, ... and so forth).
Let's take this example:
h b c d
e e g h
l l k l
m o f p
And for now, lets use the alphabet of the letters we have (usually you'd probably want to use the same whole alphabet every time):
b | c | d | e | f | g | h | k | l | m | o | p
---+---+---+---+---+---+---+---+---+---+----+----
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11
Then you make a 2D boolean array that tells whether you have a certain letter transition available:
| 0 1 2 3 4 5 6 7 8 9 10 11 <- from letter
| b c d e f g h k l m o p
-----+--------------------------------------
0 b | T T T T
1 c | T T T T T
2 d | T T T
3 e | T T T T T T T
4 f | T T T T
5 g | T T T T T T T
6 h | T T T T T T T
7 k | T T T T T T T
8 l | T T T T T T T T T
9 m | T T
10 o | T T T T
11 p | T T T
^
to letter
Now go through your word list and convert the words to transitions:
hello (6, 3, 8, 8, 10):
6 -> 3, 3 -> 8, 8 -> 8, 8 -> 10
Then check if these transitions are allowed by looking them up in your table:
[6][ 3] : T
[3][ 8] : T
[8][ 8] : T
[8][10] : T
If they are all allowed, there's a chance that this word might be found.
For example the word "helmet" can be ruled out on the 4th transition (m to e: helMEt), since that entry in your table is false.
And the word hamster can be ruled out, since the first (h to a) transition is not allowed (doesn't even exist in your table).
Now, for the probably very few remaining words that you didn't eliminate, try to actually find them in the grid the way you're doing it now or as suggested in some of the other answers here. This is to avoid false positives that result from jumps between identical letters in your grid. For example the word "help" is allowed by the table, but not by the grid.
Some further performance improvement tips on this idea:
Instead of using a 2D array, use a 1D array and simply compute the index of the second letter yourself. So, instead of a 12x12 array like above, make a 1D array of length 144. If you then always use the same alphabet (i.e. a 26x26 = 676x1 array for the standard english alphabet), even if not all letters show up in your grid, you can pre-compute the indices into this 1D array that you need to test to match your dictionary words. For example, the indices for 'hello' in the example above would be
hello (6, 3, 8, 8, 10):
42 (from 6 + 3x12), 99, 104, 128
-> "hello" will be stored as 42, 99, 104, 128 in the dictionary
Extend the idea to a 3D table (expressed as a 1D array), i.e. all allowed 3-letter combinations. That way you can eliminate even more words immediately and you reduce the number of array lookups for each word by 1: For 'hello', you only need 3 array lookups: hel, ell, llo. It will be very quick to build this table, by the way, as there are only 400 possible 3-letter-moves in your grid.
Pre-compute the indices of the moves in your grid that you need to include in your table. For the example above, you need to set the following entries to 'True':
(0,0) (0,1) -> here: h, b : [6][0]
(0,0) (1,0) -> here: h, e : [6][3]
(0,0) (1,1) -> here: h, e : [6][3]
(0,1) (0,0) -> here: b, h : [0][6]
(0,1) (0,2) -> here: b, c : [0][1]
.
:
- Also represent your game grid in a 1-D array with 16 entries and have the table pre-computed in 3. contain the indices into this array.
I'm sure if you use this approach you can get your code to run insanely fast, if you have the dictionary pre-computed and already loaded into memory.
BTW: Another nice thing to do, if you are building a game, is to run these sort of things immediately in the background. Start generating and solving the first game while the user is still looking at the title screen on your app and getting his finger into position to press "Play". Then generate and solve the next game as the user plays the previous one. That should give you a lot of time to run your code.
(I like this problem, so I'll probably be tempted to implement my proposal in Java sometime in the next days to see how it would actually perform... I'll post the code here once I do.)
UPDATE:
Ok, I had some time today and implemented this idea in Java:
class DictionaryEntry {
public int[] letters;
public int[] triplets;
}
class BoggleSolver {
// Constants
final int ALPHABET_SIZE = 5; // up to 2^5 = 32 letters
final int BOARD_SIZE = 4; // 4x4 board
final int[] moves = {-BOARD_SIZE-1, -BOARD_SIZE, -BOARD_SIZE+1,
-1, +1,
+BOARD_SIZE-1, +BOARD_SIZE, +BOARD_SIZE+1};
// Technically constant (calculated here for flexibility, but should be fixed)
DictionaryEntry[] dictionary; // Processed word list
int maxWordLength = 0;
int[] boardTripletIndices; // List of all 3-letter moves in board coordinates
DictionaryEntry[] buildDictionary(String fileName) throws IOException {
BufferedReader fileReader = new BufferedReader(new FileReader(fileName));
String word = fileReader.readLine();
ArrayList<DictionaryEntry> result = new ArrayList<DictionaryEntry>();
while (word!=null) {
if (word.length()>=3) {
word = word.toUpperCase();
if (word.length()>maxWordLength) maxWordLength = word.length();
DictionaryEntry entry = new DictionaryEntry();
entry.letters = new int[word.length() ];
entry.triplets = new int[word.length()-2];
int i=0;
for (char letter: word.toCharArray()) {
entry.letters[i] = (byte) letter - 65; // Convert ASCII to 0..25
if (i>=2)
entry.triplets[i-2] = (((entry.letters[i-2] << ALPHABET_SIZE) +
entry.letters[i-1]) << ALPHABET_SIZE) +
entry.letters[i];
i++;
}
result.add(entry);
}
word = fileReader.readLine();
}
return result.toArray(new DictionaryEntry[result.size()]);
}
boolean isWrap(int a, int b) { // Checks if move a->b wraps board edge (like 3->4)
return Math.abs(a%BOARD_SIZE-b%BOARD_SIZE)>1;
}
int[] buildTripletIndices() {
ArrayList<Integer> result = new ArrayList<Integer>();
for (int a=0; a<BOARD_SIZE*BOARD_SIZE; a++)
for (int bm: moves) {
int b=a+bm;
if ((b>=0) && (b<board.length) && !isWrap(a, b))
for (int cm: moves) {
int c=b+cm;
if ((c>=0) && (c<board.length) && (c!=a) && !isWrap(b, c)) {
result.add(a);
result.add(b);
result.add(c);
}
}
}
int[] result2 = new int[result.size()];
int i=0;
for (Integer r: result) result2[i++] = r;
return result2;
}
// Variables that depend on the actual game layout
int[] board = new int[BOARD_SIZE*BOARD_SIZE]; // Letters in board
boolean[] possibleTriplets = new boolean[1 << (ALPHABET_SIZE*3)];
DictionaryEntry[] candidateWords;
int candidateCount;
int[] usedBoardPositions;
DictionaryEntry[] foundWords;
int foundCount;
void initializeBoard(String[] letters) {
for (int row=0; row<BOARD_SIZE; row++)
for (int col=0; col<BOARD_SIZE; col++)
board[row*BOARD_SIZE + col] = (byte) letters[row].charAt(col) - 65;
}
void setPossibleTriplets() {
Arrays.fill(possibleTriplets, false); // Reset list
int i=0;
while (i<boardTripletIndices.length) {
int triplet = (((board[boardTripletIndices[i++]] << ALPHABET_SIZE) +
board[boardTripletIndices[i++]]) << ALPHABET_SIZE) +
board[boardTripletIndices[i++]];
possibleTriplets[triplet] = true;
}
}
void checkWordTriplets() {
candidateCount = 0;
for (DictionaryEntry entry: dictionary) {
boolean ok = true;
int len = entry.triplets.length;
for (int t=0; (t<len) && ok; t++)
ok = possibleTriplets[entry.triplets[t]];
if (ok) candidateWords[candidateCount++] = entry;
}
}
void checkWords() { // Can probably be optimized a lot
foundCount = 0;
for (int i=0; i<candidateCount; i++) {
DictionaryEntry candidate = candidateWords[i];
for (int j=0; j<board.length; j++)
if (board[j]==candidate.letters[0]) {
usedBoardPositions[0] = j;
if (checkNextLetters(candidate, 1, j)) {
foundWords[foundCount++] = candidate;
break;
}
}
}
}
boolean checkNextLetters(DictionaryEntry candidate, int letter, int pos) {
if (letter==candidate.letters.length) return true;
int match = candidate.letters[letter];
for (int move: moves) {
int next=pos+move;
if ((next>=0) && (next<board.length) && (board[next]==match) && !isWrap(pos, next)) {
boolean ok = true;
for (int i=0; (i<letter) && ok; i++)
ok = usedBoardPositions[i]!=next;
if (ok) {
usedBoardPositions[letter] = next;
if (checkNextLetters(candidate, letter+1, next)) return true;
}
}
}
return false;
}
// Just some helper functions
String formatTime(long start, long end, long repetitions) {
long time = (end-start)/repetitions;
return time/1000000 + "." + (time/100000) % 10 + "" + (time/10000) % 10 + "ms";
}
String getWord(DictionaryEntry entry) {
char[] result = new char[entry.letters.length];
int i=0;
for (int letter: entry.letters)
result[i++] = (char) (letter+97);
return new String(result);
}
void run() throws IOException {
long start = System.nanoTime();
// The following can be pre-computed and should be replaced by constants
dictionary = buildDictionary("C:/TWL06.txt");
boardTripletIndices = buildTripletIndices();
long precomputed = System.nanoTime();
// The following only needs to run once at the beginning of the program
candidateWords = new DictionaryEntry[dictionary.length]; // WAAAY too generous
foundWords = new DictionaryEntry[dictionary.length]; // WAAAY too generous
usedBoardPositions = new int[maxWordLength];
long initialized = System.nanoTime();
for (int n=1; n<=100; n++) {
// The following needs to run again for every new board
initializeBoard(new String[] {"DGHI",
"KLPS",
"YEUT",
"EORN"});
setPossibleTriplets();
checkWordTriplets();
checkWords();
}
long solved = System.nanoTime();
// Print out result and statistics
System.out.println("Precomputation finished in " + formatTime(start, precomputed, 1)+":");
System.out.println(" Words in the dictionary: "+dictionary.length);
System.out.println(" Longest word: "+maxWordLength+" letters");
System.out.println(" Number of triplet-moves: "+boardTripletIndices.length/3);
System.out.println();
System.out.println("Initialization finished in " + formatTime(precomputed, initialized, 1));
System.out.println();
System.out.println("Board solved in "+formatTime(initialized, solved, 100)+":");
System.out.println(" Number of candidates: "+candidateCount);
System.out.println(" Number of actual words: "+foundCount);
System.out.println();
System.out.println("Words found:");
int w=0;
System.out.print(" ");
for (int i=0; i<foundCount; i++) {
System.out.print(getWord(foundWords[i]));
w++;
if (w==10) {
w=0;
System.out.println(); System.out.print(" ");
} else
if (i<foundCount-1) System.out.print(", ");
}
System.out.println();
}
public static void main(String[] args) throws IOException {
new BoggleSolver().run();
}
}
Here are some results:
For the grid from the picture posted in the original question (DGHI...):
Precomputation finished in 239.59ms:
Words in the dictionary: 178590
Longest word: 15 letters
Number of triplet-moves: 408
Initialization finished in 0.22ms
Board solved in 3.70ms:
Number of candidates: 230
Number of actual words: 163
Words found:
eek, eel, eely, eld, elhi, elk, ern, erupt, erupts, euro
eye, eyer, ghi, ghis, glee, gley, glue, gluer, gluey, glut
gluts, hip, hiply, hips, his, hist, kelp, kelps, kep, kepi
kepis, keps, kept, kern, key, kye, lee, lek, lept, leu
ley, lunt, lunts, lure, lush, lust, lustre, lye, nus, nut
nuts, ore, ort, orts, ouph, ouphs, our, oust, out, outre
outs, oyer, pee, per, pert, phi, phis, pis, pish, plus
plush, ply, plyer, psi, pst, pul, pule, puler, pun, punt
punts, pur, pure, puree, purely, pus, push, put, puts, ree
rely, rep, reply, reps, roe, roue, roup, roups, roust, rout
routs, rue, rule, ruly, run, runt, runts, rupee, rush, rust
rut, ruts, ship, shlep, sip, sipe, spue, spun, spur, spurn
spurt, strep, stroy, stun, stupe, sue, suer, sulk, sulker, sulky
sun, sup, supe, super, sure, surely, tree, trek, trey, troupe
troy, true, truly, tule, tun, tup, tups, turn, tush, ups
urn, uts, yeld, yelk, yelp, yelps, yep, yeps, yore, you
your, yourn, yous
For the letters posted as the example in the original question (FXIE...)
Precomputation finished in 239.68ms:
Words in the dictionary: 178590
Longest word: 15 letters
Number of triplet-moves: 408
Initialization finished in 0.21ms
Board solved in 3.69ms:
Number of candidates: 87
Number of actual words: 76
Words found:
amble, ambo, ami, amie, asea, awa, awe, awes, awl, axil
axile, axle, boil, bole, box, but, buts, east, elm, emboli
fame, fames, fax, lei, lie, lima, limb, limbo, limbs, lime
limes, lob, lobs, lox, mae, maes, maw, maws, max, maxi
mesa, mew, mewl, mews, mil, mile, milo, mix, oil, ole
sae, saw, sea, seam, semi, sew, stub, swam, swami, tub
tubs, tux, twa, twae, twaes, twas, uts, wae, waes, wamble
wame, wames, was, wast, wax, west
For the following 5x5-grid:
R P R I T
A H H L N
I E T E P
Z R Y S G
O G W E Y
it gives this:
Precomputation finished in 240.39ms:
Words in the dictionary: 178590
Longest word: 15 letters
Number of triplet-moves: 768
Initialization finished in 0.23ms
Board solved in 3.85ms:
Number of candidates: 331
Number of actual words: 240
Words found:
aero, aery, ahi, air, airt, airth, airts, airy, ear, egest
elhi, elint, erg, ergo, ester, eth, ether, eye, eyen, eyer
eyes, eyre, eyrie, gel, gelt, gelts, gen, gent, gentil, gest
geste, get, gets, gey, gor, gore, gory, grey, greyest, greys
gyre, gyri, gyro, hae, haet, haets, hair, hairy, hap, harp
heap, hear, heh, heir, help, helps, hen, hent, hep, her
hero, hes, hest, het, hetero, heth, hets, hey, hie, hilt
hilts, hin, hint, hire, hit, inlet, inlets, ire, leg, leges
legs, lehr, lent, les, lest, let, lethe, lets, ley, leys
lin, line, lines, liney, lint, lit, neg, negs, nest, nester
net, nether, nets, nil, nit, ogre, ore, orgy, ort, orts
pah, pair, par, peg, pegs, peh, pelt, pelter, peltry, pelts
pen, pent, pes, pest, pester, pesty, pet, peter, pets, phi
philter, philtre, phiz, pht, print, pst, rah, rai, rap, raphe
raphes, reap, rear, rei, ret, rete, rets, rhaphe, rhaphes, rhea
ria, rile, riles, riley, rin, rye, ryes, seg, sel, sen
sent, senti, set, sew, spelt, spelter, spent, splent, spline, splint
split, stent, step, stey, stria, striae, sty, stye, tea, tear
teg, tegs, tel, ten, tent, thae, the, their, then, these
thesp, they, thin, thine, thir, thirl, til, tile, tiles, tilt
tilter, tilth, tilts, tin, tine, tines, tirl, trey, treys, trog
try, tye, tyer, tyes, tyre, tyro, west, wester, wry, wryest
wye, wyes, wyte, wytes, yea, yeah, year, yeh, yelp, yelps
yen, yep, yeps, yes, yester, yet, yew, yews, zero, zori
For this I used the TWL06 Tournament Scrabble Word List, since the link in the original question no longer works. This file is 1.85MB, so it's a little bit shorter. And the buildDictionary function throws out all words with less than 3 letters.
Here are a couple of observations about the performance of this:
It's about 10 times slower than the reported performance of Victor Nicollet's OCaml implementation. Whether this is caused by the different algorithm, the shorter dictionary he used, the fact that his code is compiled and mine runs in a Java virtual machine, or the performance of our computers (mine is an Intel Q6600 @ 2.4MHz running WinXP), I don't know. But it's much faster than the results for the other implementations quoted at the end of the original question. So, whether this algorithm is superior to the trie dictionary or not, I don't know at this point.
The table method used in checkWordTriplets() yields a very good approximation to the actual answers. Only 1 in 3-5 words passed by it will fail the checkWords() test (See number of candidates vs. number of actual words above).
Something you can't see above: The checkWordTriplets() function takes about 3.65ms and is therefore fully dominant in the search process. The checkWords() function takes up pretty much the remaining 0.05-0.20 ms.
The execution time of the checkWordTriplets() function depends linearly on the dictionary size and is virtually independent of board size!
The execution time of checkWords() depends on the board size and the number of words not ruled out by checkWordTriplets().
The checkWords() implementation above is the dumbest first version I came up with. It is basically not optimized at all. But compared to checkWordTriplets() it is irrelevant for the total performance of the application, so I didn't worry about it. But, if the board size gets bigger, this function will get slower and slower and will eventually start to matter. Then, it would need to be optimized as well.
One nice thing about this code is its flexibility:
- You can easily change the board size: Update line 10 and the String array passed to
initializeBoard().
- It can support larger/different alphabets and can handle things like treating 'Qu' as one letter without any performance overhead. To do this, one would need to update line 9 and the couple of places where characters are converted to numbers (currently simply by subtracting 65 from the ASCII value)
Ok, but I think by now this post is waaaay long enough. I can definitely answer any questions you might have, but let's move that to the comments.
