Las sopas de letras son faciles para los humanos y trivialmente faciles para las computadoras, hasta que empiezas a hacer preguntas mas interesantes. Un solucionador por fuerza bruta requiere una docena de lineas de Python. Un solucionador eficiente de multiples palabras usando un trie requiere algunas mas. Pero enmarcar el problema como una busqueda en grafos y aplicar A* en multiples dimensiones abre un territorio genuinamente novedoso: busqueda simultanea de multiples palabras, resolucion de rutas libres estilo Boggle e incluso la *generacion* de puzzles como un problema de optimizacion.
Este articulo recorre los tres niveles, con codigo funcional en cada etapa.
Nivel 1: Fuerza bruta
La sopa de letras estandar es facil de resolver exhaustivamente. Para cada palabra, prueba cada celda como punto de partida en cada direccion:
DIRECTIONS = [
(0, 1), # derecha
(0, -1), # izquierda
(1, 0), # abajo
(-1, 0), # arriba
(1, 1), # diagonal abajo-derecha
(1, -1), # diagonal abajo-izquierda
(-1, 1), # diagonal arriba-derecha
(-1, -1), # diagonal arriba-izquierda
]
def find_word(grid, word):
rows, cols = len(grid), len(grid[0])
for row in range(rows):
for col in range(cols):
for dr, dc in DIRECTIONS:
cells = []
match = True
for depth, char in enumerate(word):
nr, nc = row + dr * depth, col + dc * depth
if not (0 <= nr < rows and 0 <= nc < cols):
match = False
break
if grid[nr][nc] != char:
match = False
break
cells.append((nr, nc))
if match:
return cells
return None
Complejidad: Para una cuadricula de R filas y C columnas, W palabras cada una de longitud promedio L, el costo es O(R × C × 8 × L × W). Para nuestra cuadricula de 12x12 con 12 palabras de 7 caracteres en promedio, son alrededor de 96.768 operaciones, efectivamente instantaneo.
Nivel 2: Busqueda de multiples palabras con un Trie
Si quieres encontrar todas las palabras posibles de un diccionario ocultas en una cuadricula, verificar cada palabra por separado es ineficiente. Muchas palabras comparten prefijos. Un trie (arbol de prefijos) te permite podar la busqueda en el momento en que una ruta deja de coincidir con cualquier prefijo de palabra.
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def build_trie(words):
root = TrieNode()
for word in words:
node = root
for char in word:
node = node.children.setdefault(char, TrieNode())
node.word = word
return root
def find_all_words(grid, trie_root):
rows, cols = len(grid), len(grid[0])
found = {}
for start_row in range(rows):
for start_col in range(cols):
for dr, dc in DIRECTIONS:
node = trie_root
row, col = start_row, start_col
cells = []
while 0 <= row < rows and 0 <= col < cols:
char = grid[row][col]
if char not in node.children:
break
node = node.children[char]
cells.append((row, col))
if node.word:
found[node.word] = list(cells)
row += dr
col += dc
return found
Nivel 3: Busqueda A* en multiples dimensiones
Supongamos que quieres resolver una variante estilo Boggle: las palabras estan ocultas a lo largo de cualquier ruta conectada a traves de la cuadricula (no solo lineas rectas). Este es un problema de busqueda en grafos.
Define el espacio de estados:
- Nodo:
(fila, columna, profundidad): posicion actual en la cuadricula y cuantos caracteres de la palabra objetivo se han emparejado hasta ahora. - Estado inicial:
(fila_inicio, columna_inicio, 0)para cada celda cuyo primer caracter coincide con el primero de la palabra. - Estado objetivo: cualquier nodo donde
profundidad == len(palabra). - La heuristica para A* es el numero de caracteres restantes:
h(estado) = len(palabra) - profundidad. Esta es admisible (nunca sobreestima el costo real) porque cada paso puede emparejar como maximo un caracter. Un detalle importante:f = g + h = profundidad + (len(palabra) - profundidad) = len(palabra)es constante para todos los estados en cada nivel de profundidad, por lo que la cola de prioridad no aporta un orden util - A* con esta heuristica es equivalente a BFS. Por eso no ofrece ventaja practica sobre la fuerza bruta en sopas de letras estandar, pero el enfoque cobra valor cuando el espacio de busqueda adquiere estructura real (ver la extension multidimensional mas adelante).
import heapq
def astar_find_word(grid, word):
rows, cols = len(grid), len(grid[0])
heap = []
for row in range(rows):
for col in range(cols):
if grid[row][col] == word[0]:
g = 1
h = len(word) - g
heapq.heappush(heap, (g + h, g, row, col, 1, [(row, col)]))
while heap:
f, g, row, col, depth, path = heapq.heappop(heap)
if depth == len(word):
return path
path_set = set(path) # celdas ya usadas en esta ruta
for dr, dc in DIRECTIONS:
nr, nc = row + dr, col + dc
if not (0 <= nr < rows and 0 <= nc < cols):
continue
if (nr, nc) in path_set: # regla Boggle: no reutilizar celdas en la misma ruta
continue
if grid[nr][nc] != word[depth]:
continue
new_g = g + 1
new_h = len(word) - new_g
heapq.heappush(
heap,
(new_g + new_h, new_g, nr, nc, depth + 1, path + [(nr, nc)])
)
return None
La extension multidimensional
El espacio de estados se vuelve multidimensional para busquedas de multiples palabras simultaneas. Un estado ahora es (profundidad_0, profundidad_1, ..., profundidad_n) que representa el progreso simultaneo a traves de n palabras objetivo. A* con una heuristica conjunta apropiada (suma de caracteres restantes en todas las palabras) puede navegar esto eficientemente.
En la practica, esta formulacion es mas util para la generacion de puzzles: quieres colocar W palabras en una cuadricula de modo que se superpongan al maximo. Una variante de busqueda de haz (que mantiene solo los K estados mas prometedores en cada paso) se usa para conjuntos grandes de palabras, el mismo enfoque utilizado en la traduccion automatica y el reconocimiento de voz.
Lecturas adicionales
- Russell y Norvig, Inteligencia Artificial: Un Enfoque Moderno - el tratamiento canonico de A* y la busqueda heuristica.
- La guia de A* de Amit Patel - una excelente introduccion visual al algoritmo.
- Sedgewick y Wayne, Algoritmos (4a ed.) - para la implementacion y el analisis de tries.
Mira como estos principios de generacion se aplican al propio sistema de puzzles de Word Puzzle Hub en Como se hacen nuestros puzzles.