[pyar] Pregunta sobre algoritmo para procesar palabras en un juego

[Juan Rodríguez Monti]

Buenas lista,
Cómo va?.

Hace unos días, tenia ganas de jugar al Boggle[0]. Como no tenia a mano
ninguno, me escribí un mezclador de dados de boggle. En realidad no escribí
el juego, sólo programé lo que seria el tablero y una lógica que permite
"mezclar" los dados. Cada dado tiene 6 letras posibles, y bueno lo que hace
es ir eligiendo las letras y armar - de forma aleatoria - la distribución
de los dados en el tablero. Tiene un botoncito que dice mezclar y el
tablero armado. Es una UX sencilla. Esa parte fué fácil y rápida y anda
perfecto.

El tema es que, después de haber jugado un rato, me puse a pensar en que
estaría bueno implementar el juego completo. Y allí me encontré el motivo
de esta consulta que es el siguiente.

¿ Qué algoritmo puedo usar, o cual es la mejor manera de resolver esto,
para encontrar palabras en este tablero usando como base de referncia un
listado de palabras ?.

El tablero es así:

ANSMD
EOOES
OEOED
OPOSE
LSLSP

Son 5 filas, formadas por 5 dados cada una.

Las restricciones son: Que no es posible usar un mismo dado más de una vez
( en realidad sí se puede usar si es principio y final, pero no la
compliquemos más y supongamos que no se puede ) y que las letras que se
usan deben ser contiguas, es decir: deben tocarse. Después es posible ir
hacia arriba, abajo, derecha izquierda, diagonal, etc. Cualquier dibujo es
posible.

Lo que yo quiero saber es cómo podría implementarse la lógica para buscar
palabras allí adentro, con la posibilidad de subir, bajar, y moverse para
todos lados en el tablero al formar las palabras. El algoritmo también debe
tener una velocidad aceptable que permita jugar, también.

En realidad lo que me pareció más interesante es pensar la manera de
resolver esto. Independientemente del juego, me interesó mucho ver qué
lógica y qué algoritmo puede resolver esta situación de la mejor manera
posible.

Las palabras las voy a sacar de un archivo de texto que tiene las palabras,
formado con aspell.

Si algun día armo el juego completo, lo liberaré y será otro lindo proyecto
nacido en PyAr. Por cierto, es un juego muy divertido que lo recomiendo si
no lo conocen.

Abrazo,
Juan

[0] http://en.wikipedia.org/wiki/Boggle
-- 
Juan Rodríguez Monti

Blog: http://www.juanrodriguezmonti.com.ar
Twitter: @jrodriguezmonti
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.python.org.ar/pipermail/pyar/attachments/20130107/28c9b446/attachment.html>