Cómo encontrar la lista de posibles palabras de una matriz de letras [Boggle Solver]

Últimamente he estado jugando un juego en mi iPhone llamado Scramble. Algunos de ustedes pueden conocer este juego como Boggle. Esencialmente, cuando el juego comienza obtienes una matriz de letras como esta:

F X I E
A M L O
E W B X
A S T U

El objetivo del juego es encontrar tantas palabras como puedas que se puedan formar encadenando letras juntas. Puedes comenzar con cualquier letra, y todas las letras que la rodean son juego justo, y luego una vez que pasas a la siguiente letra, todas las letras que rodean esa letra son juego justo, excepto las letras utilizadas anteriormente. Así que en la cuadrícula de arriba, por ejemplo, podría llegar a las palabras LOB, TUX, SEA, FAME, etc. Las palabras deben tener al menos 3 caracteres, y no más de los caracteres NxN, que serían 16 en este juego, pero pueden variar en algunas implementaciones. Si bien este juego es divertido y adictivo, aparentemente no soy muy bueno en él y quería engañar un poco haciendo un programa que me diera las mejores palabras posibles (cuanto más larga sea la palabra, más puntos usted consigue).

Boggle de la muestra http://www.boggled.org/sample.gif

Desafortunadamente, no soy muy bueno con los algoritmos o sus eficiencias y así sucesivamente. Mi primer intento utiliza un diccionario como este (~2.3 MB) y hace una búsqueda lineal tratando de encontrar combinaciones con las entradas del diccionario. Esto toma un muy mucho tiempo para encontrar las palabras posibles, y como solo obtienes 2 minutos por ronda, simplemente no es adecuado.

Estoy interesado para ver si cualquier Stackoverflowers puede llegar a soluciones más eficientes. En su mayoría estoy buscando soluciones que usen Big 3 Ps: Python, PHP y Perl, aunque cualquier cosa con Java o C++ también es genial, ya que la velocidad es esencial.

SOLUCIONES ACTUALES:

• Adam Rosenfield, Python, ~20s
• John Fouhy, Python, ~3s {[29]]} Kent Fredric, Perl, ~1s {[29]]}
• Darius Bacon, Python, ~1s
• rvarcher, VB.NET (enlace en vivo) , ~1s
• Paolo Bergantino, PHP (enlace en vivo) , ~5s (~2s localmente)

BOUNTY :

Estoy agregando una recompensa a esta pregunta como mi forma de agradecer a todas las personas que colaboraron con sus programas. Desafortunadamente, solo puedo dar la respuesta aceptada a uno de ustedes, así que mediré quién tiene el solucionador de boggle más rápido en 7 días a partir de ahora y premiaré al ganador con la recompensa.

Recompensa otorgada. Gracias a todos los que participaron.