¿Cómo puedo encontrar las palabras válidas en una cuadrícula de caracteres?

Estoy creando un juego similar a Tetris, con dos diferencias principales: la pantalla ya comienza llena de mosaicos (como en Puzzle Quest para Nintendo DS y PC) y cada mosaico individual tiene una letra. El objetivo del jugador es eliminar fichas formando palabras válidas con ellas. Las palabras se forman colocando letras una al lado de la otra, en cualquier dirección, excepto en diagonal.

El jugador puede mover una fila completa de fichas hacia la izquierda o hacia la derecha o una columna completa de fichas hacia arriba o hacia abajo, durante todos los espacios que desee (si el movimiento de una fila / columna supera los límites del tablero, el la letra que cruza el límite "ciclo", que aparece en el otro extremo de la fila / columna). Después de la acción del jugador, el juego debe revisar todo el tablero para buscar palabras válidas y eliminar las letras que forman esas palabras del tablero. Las letras sobre las que se eliminaron se colocarán en el lugar de las letras que se eliminaron y nuevas letras caerán desde la parte superior de la pantalla hasta que el tablero se vuelva a llenar.

Ya he escrito un algoritmo lineal que, dada una secuencia de caracteres, determina si es una palabra inglesa válida. El problema que tengo es: ¿cómo puedo verificar si hay palabras válidas en la pizarra? ¿Es la fuerza bruta la única forma? Probar todas las combinaciones posibles del tablero para ver si son válidas es muy lento, incluso para un tablero pequeño (5x5). Cualquier ayuda será muy apreciada, gracias!

La fuerza bruta no es la única forma.

Resolver su tablero de juego es similar a resolver un tablero de Boggle , pero más simple. Desea verificar cada mosaico en el tablero, para ver si hay palabras que puedan formarse siguiendo las instrucciones apropiadas.

Todavía le gustaría refinar aún más su espacio de búsqueda para no molestarse en buscar en una dirección si sabe que no puede pronunciar una palabra. Por ejemplo, si encuentra dos qs seguidos, debe abortar. Para ese fin, querrá algún tipo de estructura de datos que le permita saber si un conjunto de caracteres es el prefijo de una palabra válida. Para esto, puedes usar un trie o árbol de prefijos; Una estructura de datos útil para resolver problemas como este.

Un árbol de prefijos es una estructura jerárquica basada en nodos, donde cada nodo representa algún prefijo de sus hijos, y los nodos hoja (generalmente) representan los valores finales. Por ejemplo, si su diccionario de palabras válidas contiene "cat", "car" y "cell", un trie podría verse así:

    0        The root of the trie is the empty string here, although you 
    |        can implement the structure differently if you want.
    c
   / \ 
  a   e
 / \   \
t  r    l
         \
          l

Por lo tanto, comienza llenando un árbol de prefijos con cada palabra válida en tu juego.

El proceso real de encontrar palabras válidas en el tablero en cualquier momento implicará iniciar una búsqueda recursiva desde cada mosaico en el tablero. Debido a que cada búsqueda a través del espacio del tablero que comienza en algún mosaico dado es independiente, estos pueden ser paralelos si es necesario. A medida que busca, "sigue" el árbol de prefijos en función del valor de la letra en la dirección que está buscando.

Eventualmente llegará a un punto donde ninguna de las letras circundantes son hijos de su nodo de árbol de prefijos actual. Cuando llegue a ese punto, si también es cierto que el nodo actual es una hoja, ha encontrado una palabra válida. De lo contrario, no ha encontrado una palabra válida y puede cancelar la búsqueda.

El código de ejemplo y una discusión de esta técnica (y otras, como una solución de programación dinámica que puede ser aún más rápida al "invertir" el espacio de búsqueda de una manera) se pueden encontrar en el blog de este compañero aquí ; habla sobre resolver Boggle, pero adaptar las soluciones a su juego es más o menos una cuestión de cambiar en qué direcciones permite que ocurra la búsqueda.

Es posible que hayas intentado esto, ya lo hayas implementado, quizás mejor acompañado de otra respuesta, etc. Pero no los vi mencionados (todavía), así que aquí está:

Puede descartar muchas de las comprobaciones haciendo un seguimiento de lo que cambió y lo que no. Por ejemplo:

On a 5x5 field, A vertical word is found on base of the third column,
All the rows change. However, the first, second, fourth, and fifth,
columns do not change, so you dont need to worry about them (the third did change.)

On a 5x5 field, A 3 letter word is found horizontally on row 2, column 3, to column 5.
So you need to check row 1 and 2 (row 1 because the words on that one
fell down and where replaced), as-well as columns 3, 4, and 5.

o, en psudocódigo

// update the board

// and check
if (vertical_word)
{
    check(updated_column)

    for (i in range 0 to updated_row_base)
        check(i)
}
else // horizontal word
{
    for (i in range 0 to updated_row)
        check(i)

    for (i in range 0 to updated_column_start)
        check(i)

    for (i in range updated_column_end+1 to final_column)
        check(i)
}

Y las preguntas triviales:

¿Tiene configurados los optimizadores de velocidad de compilación? (si estás usando uno)

¿Se puede optimizar su algoritmo de búsqueda de palabras? ¿De cualquier manera?

Recuerda que cada personaje es un valor. Así que usa eso para tu ventaja. Hay algunas funciones hash que podrían calcularse rápidamente al iterar en subcadenas. Por ejemplo, supongamos que le damos a cada letra un código de 5 bits (solo c - 'a' + 1en C):

space = 00000;
a = 00001;
c = 00011;
e = 00101;
t = 01100;

De lo que podría pasar rápidamente por todas las subcadenas de cierto tamaño:

a b [c a t] e t h e = 00011 00001 01100;
//Now we just remove the 5 msb and shfit the rest 5 bits left and add the new character.
a b  c [a t e] t h e = (([c a t] & 0xffff) << 5) | e; // == a t e

Podemos verificar las subcadenas de hasta 12 letras de esta manera en las arquitecturas más comunes hoy en día.

Si existe un código hash en su diccionario, puede extraer la palabra de allí rápidamente porque los códigos hash como este son únicos. Cuando alcanza el máximo de 12 letras, es posible que desee agregar otras estructuras de datos para las palabras que comienzan con esas 12 letras. Si encuentra una palabra que comienza con 12 letras específicas, simplemente cree una lista u otra pequeña tabla hash para los sufijos de cada palabra que comience con ese prefijo.

Almacenar un diccionario de todos los códigos de palabras existentes no debe tomar más de unos pocos megabytes de memoria.

¿Estás limitado solo a las formas clásicas de Tetris al formar palabras, o alguna formación lo hará? ¿Pueden las palabras doblarse indefinidamente o solo una vez? ¿Puede una palabra ser tan larga como quiera? Esto se vuelve bastante complejo si puede hacer tantas curvas como desee, haciendo que las palabras más largas posibles sean de 25 caracteres. Supongo que tienes una lista de palabras aceptadas. En ese supuesto, le sugiero que pruebe algo como esto:

At the start of the game:
  Iterate tiles:
    Use tile as starting letter
      Store previous tile
      Check the four adjacent tiles
      If a tile can continue a word started by the previous tile, carry on
      Store the next tile
      Move check to next tile

Esto creará un mapa en cada mosaico con información sobre cómo se conecta este mosaico a las palabras que lo rodean en la cuadrícula. Cuando se mueve una columna o fila, verifique todos los mosaicos que hayan estado o estén adyacentes al movimiento y vuelva a calcular la información. Cuando encuentra una palabra, y no se pueden agregar más mosaicos a esa palabra; eliminarlo No estoy seguro de si esto será más rápido, realmente se reduce a cuántas palabras se crean a medias. El beneficio de esto es que lo más probable es que el usuario intente crear una palabra a partir de media palabra completa en el tablero. Al mantener todas estas palabras almacenadas, es fácil verificar si una palabra se ha completado.