Lately I have been playing a game on my iPhone called Scramble. Some of you may know this game as Boggle. Essentially, when the game starts you get a matrix of letters like so:

    F X I E
    A M L O
    E W B X
    A S T U

The goal of the game is to find as many words as you can that can be formed by chaining letters together. You can start with any letter, and all the letters that surround it are fair game, and then once you move on to the next letter, all the letters that surround that letter are fair game, **except for any previously used letters**. So in the grid above, for example, I could come up with the words `LOB`, `TUX`, `SEA`, `FAME`, etc. Words must be at least 3 characters, and no more than NxN characters, which would be 16 in this game but can vary in some implementations.  While this game is fun and addictive, I am apparently not very good at it and I wanted to cheat a little bit by making a program that would give me the best possible words (the longer the word the more points you get).

[![Sample Boggle][1]][1]  
&lt;sub&gt;(source: [boggled.org](http://www.boggled.org/sample.gif))&lt;/sub&gt;  

I am, unfortunately, not very good with algorithms or their efficiencies and so forth. My first attempt uses a dictionary [such as this one](http://www.freebsd.org/cgi/cvsweb.cgi/src/share/dict/web2?rev=1.12;content-type=text%2Fplain) (~2.3MB) and does a linear search trying to match combinations with dictionary entries. This takes a _very_ long time to find the possible words, and since you only get 2 minutes per round, it is simply not adequate.

I am interested to see if any Stackoverflowers can come up with more efficient solutions. I am mostly looking for solutions using the Big 3 Ps: Python, PHP, and Perl, although anything with Java or C++ is cool too, since speed is essential.

**CURRENT SOLUTIONS**:

- [Adam Rosenfield](#746102), Python, ~20s  
- [John Fouhy](#746345), Python, ~3s  
- [Kent Fredric](#746955), Perl, ~1s  
- [Darius Bacon](#750012), Python, ~1s  
- [rvarcher](#750722), VB.NET, ~1s
- [Paolo Bergantino](#757165), PHP [(live link)](http://www.rootspot.com/stackoverflow/boggle.php), ~5s (~2s locally)


 [1]: https://i.stack.imgur.com/qLLPp.gif

All Boggle Solutions on Gang of Coders

Total of 1 Boggle Solutions

How to find list of possible words from a letter matrix [Boggle Solver]