ALGORITMO PARA RESOLVER UNA SOPA DE LETRAS USANDO BACKTRACKING E INDICE INVERTIDO

En cierta ocasión, mi padre me llevo a conocer al hijo de un amigo, que trabaja como ingeniero desarrollador en una de las empresas de software más reconocidas en la ciudad de Barranquilla. Nos comentaba él, de los procesos por los que pasaba el aspirante para aplicar a un puesto en el área de desarrollo. Relataba que hacían una entrevista preliminar, luego les hacían una prueba psicotécnica (bastante aburrida considero yo), un test teórico, y finalmente un test de lógica algorítmica. La verdad, no estaba interesado para aplicar al puesto de desarrollador, pero me dedique a escuchar atentamente lo que decía, y me llamo mucho la atención el test de lógica algorítmica. Había pasado mucho tiempo que no desarrollaba algún algoritmo lo suficientemente sencillo y que requiriera de mucha lógica, por lo tanto se pueden imaginar como me sentía, bastante ansioso, así que le pregunté en que consistía el test de algoritmia.

De manera general, dice, la prueba era de dos horas, y básicamente el test consistía en desarrollar un algoritmo que permitiera darle solución a una sopa de letras. Luego comenzó a hablarnos de la forma en que pudo solucionar el problema. Después de tres horas de charlar con el hijo del señor Janestal, mi padre y yo le agradecimos su información, y nos fuimos. Pero me quedó una gran inquietud, me pareció bastante interesante desarrollar un algoritmo que de solución a una Sopa de letras. Así que decidí implementar mi propio algoritmo de solución. No fue sencillo, pues yo no tengo muy buenos hábitos para estas cosas, me tomó casi una semana para dar con la solución, yo creo que si hubiese aplicado al test de algoritmia en esa empresa, me hubiesen tenido que dar el mismo tiempo, 1 semana. Así que ahora quiero compartir con ustedes mi solución, y hacerles caer en cuenta que la solución, no solo implica la mejor búsqueda, sino también la mejor optimización de recursos en memoria y el mejor uso de la CPU.

Para empezar, he querido dividir esta entrega en varios capítulos donde me enfocaré en cada una de las etapas por las que tuve que pasar para solucionar el “pequeño” problema. Aquí les dejo la primera parte: analisis de dominio.

1. ANALISIS DE DOMINIO PARA LA SOPA DE LETRAS.

Para comenzar con la solución, hice un análisis profundo del avance tecnológico que existe actualmente en la solución de este tipo de puzzle (rompecabezas). Empezaré por definir que es una sopa de letras, pues para aquellos que estén interesados.

1.1 ¿QUE ES UNA SOPA DE LETRAS?

En la figura que verán a continuación, se muestra un ejemplo de una sopa de letras.


Una sopa de letras se puede definir como un juego de destreza y rapidez mental, donde se tiene que encontrar un número finito de palabras. Dichas palabras están definidas previamente en el mismo juego y están ocultas en una matriz cuadrada de letras. La búsqueda de las palabras en la matriz se puede realizar de la siguiente forma:


En la figura anterior se puede observar la forma de buscar una palabra en la matriz de letras, para este caso la palabra a buscar es “NADIE”.

1.2 ALGORITMOS DESARROLLADOS PARA LA SOLUCION DE SOPA DE LETRAS.

Haciendo mis investigaciones, y estableciendo un estado del arte de estos aspectos, me encontré con que algunas de las aplicaciones que le dan solución a una sopa de letras lo hacen por medio de la técnica llamada backtracking (vuelta atrás). Es una estrategia para encontrar soluciones a problemas que satisfacen restricciones, usada muy frecuentemente en sistema multi-soluciones. Uno de los ejemplos que podemos encontrar en la aplicación de este algoritmo para el contexto que estamos tratando, es la solución del famoso sudoku, o encontrar el camino que da la salida en un laberinto, o en un juego de ajedrez, podíamos usarlo para aplicarle cierta inteligencia artificial a la CPU. El backtracking también es usado como base lógica en sistemas de reglas de inferencia, como es el caso de prolog. Para más información, aquí les dejo de la wikipedia, más información básica, aunque no confiable, de cómo funciona esta técnica. http://es.wikipedia.org/wiki/Vuelta_Atrás.

1.3 SOLUCION ACTUAL PROPUESTA

Aunque la solución que propone el backtracking parece ser buena frente a otras alternativas de búsqueda para este tipo de aplicaciones, el tiempo de respuesta puede variar dependiendo del tamaño de la matriz. Las causas de esta característica radican en la forma de implementación, y si no se usa otra técnica que lo complemente para dar con la solución, puede consumir mayor tiempo para encontar las respuestas. Por ejemplo, si intentáramos solucionar la sopa de letra con la única implementación del backtracking tendríamos entonces que:

1-Comparar cada letra de la matriz, verificar si dicha letra es igual a la primera letra de la palabra buscada.

2-Si es igual entonces:

3-Seleccionar una de las direcciones: (ABAJO,ARRIBA, DERECHA, IZQUIERDA,DIAGONAL_INFERIOR_IZQUIERDA, DIAGONAL_INFERIOR_DERECHA, DIAGONAL_SUPERIOR_DERECHA, DIAGONAL_SUPERIOR_IZQUIERDA).

4-verificar la siguiente letra de la palabra buscada en una de las direcciones seleccionada.

5-Si es igual entonces: ir al paso 4.

6-No es igual entonces: ir al paso 3.

7-Si ya no hay mas letras que buscar en la palabra buscada, entonces la palabra ha sido encontrada en la dirección seleccionada y en la posición de letra de la matriz comparada. ir al paso 9.

8-Si ya no hay mas direcciones en donde buscar la solución entonces ir al paso 1.

9-Si existen mas palabras por buscar, Pasar a la siguiente palabra buscada.

10-No existen más palabras por buscar, entonces debemos mostrar las soluciones encontradas.

Continúa con la segunda parte de esta entrega.