Estoy haciendo un juego de palabras similar al boggle. El usuario se le da una cuadrícula de letras como esto:Algoritmo para elegir letras al azar para el juego de búsqueda de palabras que permite que se deletreen muchas palabras
O V Z W X
S T A C K
Y R F L Q
El usuario escoge una palabra utilizando cualquier cadenas adyacentes de letras, como la palabra "pila" a través de la línea media. Las letras utilizadas son reemplazadas por la máquina, p. (nuevas letras en minúsculas):
O V Z W X
z e x o p
Y R F L Q
Aviso ahora puede significar un "desbordamiento" mediante el uso de las nuevas letras. Mi problema es: ¿qué algoritmo puedo usar para elegir nuevas letras que maximicen el número de palabras largas que el usuario puede deletrear? Quiero que el juego sea divertido e implique la ortografía, p. Algunas veces, las palabras de 6 letras pero, si eliges letras malas, los juegos implican que el usuario solo deletree palabras de 3 letras y no tenga la oportunidad de encontrar palabras más grandes.
Por ejemplo:
Se podía elegir aleatoriamente nuevas letras del alfabeto. Esto no funciona bien
Del mismo modo, encontré escoger al azar, pero utilizando las frecuencias de letras de Scrabble no funcionó bien. Esto funciona mejor en Scrabble, creo que ya que tienes menos restricciones sobre el orden en que usas las letras.
Intenté tener un conjunto de listas, cada una representando uno de los dados del juego Boggle, y cada letra sería escogidos de un lado dado al azar (también me pregunto si puedo usar legalmente estos datos en un producto). No noté que esto funcionaba bien. Imagino que los lados dados de Boggle fueron elegidos de una manera sensata, pero no puedo encontrar cómo se hizo esto.
Algunas ideas que hemos considerado:
hacer una tabla de la frecuencia con pares de letras se presentan juntos en el diccionario. En aras de la discusión, digamos que E se ve al lado de A el 30% del tiempo. Al elegir una nueva carta, elegiría aleatoriamente una letra basada en la frecuencia de esta carta que aparece junto a una letra adyacente elegida al azar en la cuadrícula. Por ejemplo, si la letra vecina era E, la nueva letra sería "A" el 30% del tiempo. El debería significar que hay muchos pares decentes para usar dispersos por el mapa. Tal vez podría mejorar esto haciendo que las tablas de probabilidad de una carta ocurran entre otras dos letras.
De alguna manera hacer una búsqueda de lo que las palabras pueden ser escritas en la parrilla actual, teniendo las nuevas letras para ser comodines. Luego reemplazaría los comodines con letras que permitieran escribir las palabras más grandes. Sin embargo, no estoy seguro de cómo lo haría de manera eficiente.
Se agradecen otras ideas. Me pregunto si hay una forma común de resolver este problema y qué otros juegos de palabras usan.
Edit: ¡Gracias por las excelentes respuestas hasta ahora! Olvidé mencionar que realmente estoy buscando requisitos de memoria/CPU bajos si es posible, probablemente usaré el diccionario SOWPODS (aproximadamente 250,000) y mi cuadrícula podrá 6 x 6.
Me gusta su idea de usar probabilidades de yuxtaposición de letras. Podrías expandirlo aún más: para cualquier ubicación de letra dada, calcula la probabilidad de que cada letra sea adyacente a las letras que las rodean inmediatamente y promedia estas probabilidades en una sola, luego escoge una letra aleatoria usando las probabilidades promediadas como ponderaciones. – Cameron