Comprobación del azulejo de Scrabble

Question

Para el control de baldosas en scrabble, se hacen cuatro cuadrículas de letras de 5x5 por un total de 100 fichas. Me gustaría hacer uno donde las 40 palabras horizontales y verticales sean válidas. El conjunto de baldosas disponibles contiene:

• 12 x E
• 9 x A, I
• 8 x O
• 6 x N, R, T
• 4 x D, L, S , U
• 3 x G
• 2 x B, C, F, H, M, P, V, W, Y, azulejo blanco (wildcard)
• 1 x K, J, Q, X, Z

El diccionario de palabras válidas está disponible here (700KB). Hay aproximadamente 12,000 palabras válidas de 5 letras.

Aquí hay un ejemplo donde todas las 20 palabras horizontales son válidas:

Z O W I E|P I N O T 
Y O G I N|O C t A D <= blank being used as 't' 
X E B E C|N A L E D 
W A I T E|M E R L E 
V I N E R|L U T E A 
---------+--------- 
U S N E A|K N O S P 
T A V E R|J O L E D 
S O F T A|I A M B I 
R I D G Y|H A I T h <= blank being used as 'h' 
Q U R S H|G R O U F 

Me gustaría crear una donde todos los verticales son también válidas. ¿Puedes ayudarme a resolver esto? No es tarea. Es una pregunta con la que un amigo me pidió ayuda.

Answer 1

Final Edit: Resuelto! Aquí hay una solución.

GNAWN|jOULE 
RACHE|EUROS 
IDIOT|STEAN 
PINOT|TRAvE 
TRIPY|SOLES 
-----+----- 
HOWFF|ZEBRA 
AGILE|EQUID 
CIVIL|BUXOM 
EVENT|RIOJA 
KEDGY|ADMAN 

Aquí hay una foto de ella construida con mi conjunto de scrabble. http://twitpic.com/3wn7iu

Este fue fácil de encontrar una vez que tuve el enfoque correcto, así que apuesto a que podría encontrar muchos más de esta manera. Vea a continuación la metodología.

---

Construya un árbol de prefijos del diccionario de 5 palabras para cada fila y columna. Recíprocamente, una ubicación de mosaico dada es válida si forma prefijos válidos para su columna y fila, y si el mosaico está disponible, y si la colocación de la siguiente tesela es válida. El caso base es que es válido si no queda espacio para colocar.

Probablemente tenga sentido encontrar todas las placas válidas de 5x5, como dijo Glenn, y ver si se pueden combinar cuatro de ellas. Recordar a una profundidad de 100 no suena como diversión.

Editar: Aquí está la versión 2 de mi código para esto.

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <stdbool.h> 

typedef union node node; 
union node { 
    node* child[26]; 
    char string[6]; 
}; 

typedef struct snap snap; 
struct snap { 
    node* rows[5]; 
    node* cols[5]; 
    char tiles[27]; 
    snap* next; 
}; 

node* root; 
node* vtrie[5]; 
node* htrie[5]; 
snap* head; 

char bag[27] = {9,2,2,4,12,2,3,2,9,1,1,4,2,6,8,2,1,6,4,6,4,2,2,1,2,1,2}; 
const char full_bag[27] = {9,2,2,4,12,2,3,2,9,1,1,4,2,6,8,2,1,6,4,6,4,2,2,1,2,1,2}; 
const char order[26] = {16,23,9,25,21,22,5,10,1,6,7,12,15,2,24,3,20,13,19,11,8,17,14,0,18,4}; 

void insert(char* string){ 
    node* place = root; 
    int i; 
    for(i=0;i<5;i++){ 
     if(place->child[string[i] - 'A'] == NULL){ 
      int j; 
      place->child[string[i] - 'A'] = malloc(sizeof(node)); 
      for(j=0;j<26;j++){ 
       place->child[string[i] - 'A']->child[j] = NULL; 
      } 
     } 
     place = place->child[string[i] - 'A']; 
    } 
    memcpy(place->string, string, 6); 
} 

void check_four(){ 
    snap *a, *b, *c, *d; 
    char two_total[27]; 
    char three_total[27]; 
    int i; 
    bool match; 
    a = head; 
    for(b = a->next; b != NULL; b = b->next){ 
     for(i=0;i<27; i++) 
      two_total[i] = a->tiles[i] + b->tiles[i]; 
     for(c = b->next; c != NULL; c = c->next){ 
      for(i=0;i<27; i++) 
       three_total[i] = two_total[i] + c->tiles[i]; 
      for(d = c->next; d != NULL; d = d->next){ 
       match = true; 
       for(i=0; i<27; i++){ 
        if(three_total[i] + d->tiles[i] != full_bag[i]){ 
         match = false; 
         break; 
        } 
       } 
       if(match){ 
        printf("\nBoard Found!\n\n"); 
        for(i=0;i<5;i++){ 
         printf("%s\n", a->rows[i]->string); 
        } 
        printf("\n"); 
        for(i=0;i<5;i++){ 
         printf("%s\n", b->rows[i]->string); 
        } 
        printf("\n"); 
        for(i=0;i<5;i++){ 
         printf("%s\n", c->rows[i]->string); 
        } 
        printf("\n"); 
        for(i=0;i<5;i++){ 
         printf("%s\n", d->rows[i]->string); 
        } 
        exit(0); 
       } 
      } 
     } 
    } 
} 

void snapshot(){ 
    snap* shot = malloc(sizeof(snap)); 
    int i; 
    for(i=0;i<5;i++){ 
     printf("%s\n", htrie[i]->string); 
     shot->rows[i] = htrie[i]; 
     shot->cols[i] = vtrie[i]; 
    } 
    printf("\n"); 
    for(i=0;i<27;i++){ 
     shot->tiles[i] = full_bag[i] - bag[i]; 
    } 
    bool transpose = false; 
    snap* place = head; 
    while(place != NULL && !transpose){ 
     transpose = true; 
     for(i=0;i<5;i++){ 
      if(shot->rows[i] != place->cols[i]){ 
       transpose = false; 
       break; 
      } 
     } 
     place = place->next; 
    } 
    if(transpose){ 
     free(shot); 
    } 
    else { 
     shot->next = head; 
     head = shot; 
     check_four(); 

    } 
} 

void pick(x, y){ 
    if(y==5){ 
     snapshot(); 
     return; 
    } 
    int i, tile,nextx, nexty, nextz; 
    node* oldv = vtrie[x]; 
    node* oldh = htrie[y]; 
    if(x+1==5){ 
     nexty = y+1; 
     nextx = 0; 
    } else { 
     nextx = x+1; 
     nexty = y; 
    } 
    for(i=0;i<26;i++){ 
     if(vtrie[x]->child[order[i]]!=NULL && 
      htrie[y]->child[order[i]]!=NULL && 
      (tile = bag[i] ? i : bag[26] ? 26 : -1) + 1) { 
       vtrie[x] = vtrie[x]->child[order[i]]; 
       htrie[y] = htrie[y]->child[order[i]]; 
       bag[tile]--; 

       pick(nextx, nexty); 

       vtrie[x] = oldv; 
       htrie[y] = oldh; 
       bag[tile]++; 
      } 
    } 
} 

int main(int argc, char** argv){ 
    root = malloc(sizeof(node)); 
    FILE* wordlist = fopen("sowpods5letters.txt", "r"); 
    head = NULL; 
    int i; 
    for(i=0;i<26;i++){ 
     root->child[i] = NULL; 
    } 
    for(i=0;i<5;i++){ 
     vtrie[i] = root; 
     htrie[i] = root; 
    } 

    char* string = malloc(sizeof(char)*6); 
    while(fscanf(wordlist, "%s", string) != EOF){ 
     insert(string); 
    } 
    free(string); 
    fclose(wordlist); 
    pick(0,0); 

    return 0; 
} 

Esto intenta las letras poco frecuentes primero, que ya no estoy seguro de que sea una buena idea. Comienza a empantanarse antes de que salga de las tablas comenzando con x. Después de ver cuántos bloques de 5x5 había, modifiqué el código para enumerar todos los bloques válidos de 5x5. Ahora tengo un archivo de texto de 150 MB con todas las 4,430,974 soluciones de 5x5.

También lo probé con solo recurrir a través de los 100 mosaicos completos, y eso todavía se está ejecutando.

Edición 2: Aquí está la lista de todos los bloques 5x5 válidos que generé. http://web.cs.sunyit.edu/~levyt/solutions.rar

Editar 3: Hmm, parece que hubo un error en el seguimiento del uso de mosaicos, porque acabo de encontrar un bloque en mi archivo de salida que usa 5 Zs.

COSTE 
ORCIN 
SCUZZ 
TIZZY 
ENZYM 

Editar 4: Aquí está el producto final.

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <stdbool.h> 

typedef union node node; 
union node { 
    node* child[26]; 
    char string[6]; 
}; 

node* root; 
node* vtrie[5]; 
node* htrie[5]; 
int score; 
int max_score; 

char block_1[27] = {4,2,0,2, 2,0,0,0,2,1,0,0,2,1,2,0,1,2,0,0,2,0,0,1,0,1,0};//ZEBRA EQUID BUXOM RIOJA ADMAN 
char block_2[27] = {1,0,1,1, 4,2,2,1,3,0,1,2,0,1,1,0,0,0,0,1,0,2,1,0,1,0,0};//HOWFF AGILE CIVIL EVENT KEDGY 
char block_3[27] = {2,0,1,1, 1,0,1,1,4,0,0,0,0,3,2,2,0,2,0,3,0,0,1,0,1,0,0};//GNAWN RACHE IDIOT PINOT TRIPY 
                      //JOULE EUROS STEAN TRAVE SOLES 
char bag[27] =  {9,2,2,4,12,2,3,2,9,1,1,4,2,6,8,2,1,6,4,6,4,2,2,1,2,1,2}; 
const char full_bag[27] = {9,2,2,4,12,2,3,2,9,1,1,4,2,6,8,2,1,6,4,6,4,2,2,1,2,1,2}; 
const char order[26] = {16,23,9,25,21,22,5,10,1,6,7,12,15,2,24,3,20,13,19,11,8,17,14,0,18,4}; 
const int value[27] = {244,862,678,564,226,1309,844,765,363,4656,909,414,691,463,333,687,11998,329,218,423,536,1944,1244,4673,639,3363,0}; 

void insert(char* string){ 
    node* place = root; 
    int i; 
    for(i=0;i<5;i++){ 
     if(place->child[string[i] - 'A'] == NULL){ 
      int j; 
      place->child[string[i] - 'A'] = malloc(sizeof(node)); 
      for(j=0;j<26;j++){ 
       place->child[string[i] - 'A']->child[j] = NULL; 
      } 
     } 
     place = place->child[string[i] - 'A']; 
    } 
    memcpy(place->string, string, 6); 
} 

void snapshot(){ 
    static int count = 0; 
    int i; 
    for(i=0;i<5;i++){ 
     printf("%s\n", htrie[i]->string); 
    } 
    for(i=0;i<27;i++){ 
      printf("%c%d ", 'A'+i, bag[i]); 
    } 
    printf("\n"); 
    if(++count>=1000){ 
     exit(0); 
    } 
} 


void pick(x, y){ 
    if(y==5){ 
     if(score>max_score){ 
      snapshot(); 
      max_score = score; 
     } 
     return; 
    } 
    int i, tile,nextx, nexty; 
    node* oldv = vtrie[x]; 
    node* oldh = htrie[y]; 
    if(x+1==5){ 
     nextx = 0; 
     nexty = y+1; 
    } else { 
     nextx = x+1; 
     nexty = y; 
    } 
    for(i=0;i<26;i++){ 
     if(vtrie[x]->child[order[i]]!=NULL && 
      htrie[y]->child[order[i]]!=NULL && 
      (tile = bag[order[i]] ? order[i] : bag[26] ? 26 : -1) + 1) { 
       vtrie[x] = vtrie[x]->child[order[i]]; 
       htrie[y] = htrie[y]->child[order[i]]; 
       bag[tile]--; 
       score+=value[tile]; 

       pick(nextx, nexty); 

       vtrie[x] = oldv; 
       htrie[y] = oldh; 
       bag[tile]++; 
       score-=value[tile]; 
      } 
    } 
} 

int main(int argc, char** argv){ 
    root = malloc(sizeof(node)); 
    FILE* wordlist = fopen("sowpods5letters.txt", "r"); 
    score = 0; 
    max_score = 0; 
    int i; 
    for(i=0;i<26;i++){ 
     root->child[i] = NULL; 
    } 
    for(i=0;i<5;i++){ 
     vtrie[i] = root; 
     htrie[i] = root; 
    } 
    for(i=0;i<27;i++){ 
     bag[i] = bag[i] - block_1[i]; 
     bag[i] = bag[i] - block_2[i]; 
     bag[i] = bag[i] - block_3[i]; 

     printf("%c%d ", 'A'+i, bag[i]); 
    } 

    char* string = malloc(sizeof(char)*6); 
    while(fscanf(wordlist, "%s", string) != EOF){ 
     insert(string); 
    } 
    free(string); 
    fclose(wordlist); 
    pick(0,0); 

    return 0; 
} 

después de descubrir cuántos bloques hay (casi 2 mil millones y sigue contando), me pasa a tratar de encontrar ciertos tipos de bloques, en particular la difícil construir unidades usando las letras poco comunes. Mi esperanza era que si terminaba con un conjunto bastante benigno de cartas yendo al último bloque, el vasto espacio de bloques válidos probablemente tendría uno para ese conjunto de letras.

Asigné a cada tesela un valor inversamente proporcional al número de 5 letras en las que aparece. Luego, cuando encontré un bloque válido resumiría los valores del mosaico, y si el puntaje era el mejor que había visto hasta ahora , Imprimiría el bloque.

Para el primer bloque eliminé las fichas en blanco, pensando que el último bloque necesitaría más esa flexibilidad. Después de dejar que se ejecutara hasta que no había visto un bloque mejor aparecer durante algún tiempo, seleccioné el mejor bloque y quité las fichas de la bolsa, y ejecuté el programa nuevamente, obteniendo el segundo bloque. Repetí esto para el 3er bloque. Luego, para el último bloque, agregué los espacios en blanco y usé el primer bloque válido que encontró.

Answer 2

Me acercaría al problema (ingenuamente, para estar seguro) teniendo una visión pesimista. Intentaría probar que no había una solución de 5x5, y por lo tanto, ciertamente no cuatro soluciones 5x5. Para probar que no había una solución 5x5, intentaría construir una desde todas las posibilidades. Si mi conjetura fallara y pudiera construir una solución de 5x5, entonces, tendría una forma de construir soluciones 5x5 y trataría de construir todas de las soluciones (independientes) 5x5. Si hubiera al menos 4, entonces determinaría si alguna combinación cumple con las restricciones de conteo de letras.

[Editar] El conjunto nulo ha determinado que hay "4,430,974 soluciones 5x5". ¿Son estos válidos? Quiero decir que tenemos una limitación en la cantidad de letras que podemos usar. Esta limitación se puede expresar como un vector de límite BV = [9, 2, 2, 4, ...] correspondiente a los límites de A, B, C, etc. (Verá este vector en el código del Conjunto nulo). Una solución de 5x5 es válida si cada término de su vector de conteo de letras es menor que el término correspondiente en BV. Sería fácil verificar si una solución de 5x5 es válida tal como fue creada. Tal vez el número 4,430,974 se puede reducir, por ejemplo, N.

Independientemente, podemos indicar el problema de la siguiente manera: encuentre cuatro vectores de conteo de letras entre los N cuya suma sea igual a BV. Hay (N, 4) posibles sumas ("N elige 4"). Con N igual a 4 millones, esto todavía está en el orden de 10^25 --- no es un número alentador. Quizás podría buscar cuatro cuyos primeros términos sumen a 9, y si es así verificar que sus segundos términos sumen a 2, etc.

Me gustaría comentar que después de elegir 4 de N los cálculos son independientes, entonces si tiene una máquina multinúcleo puede hacer que esto vaya más rápido con una solución paralela.

[Editar2] Paralelizar probablemente no haría mucha diferencia, sin embargo. En este punto, podría tener una visión optimista: ciertamente hay más soluciones 5x5 de lo que esperaba, por lo que puede haber más soluciones finales de lo esperado. Tal vez no tenga que llegar muy lejos en el 10^25 para golpear a uno.

Answer 3

Así es como probaría esto. Primero construye un árbol de prefijo.

Elija una palabra y colóquela horizontalmente en la parte superior. Elija una palabra y colóquela verticalmente. Alternarlos hasta opciones agotadas.Al alternar, comienzas a corregir las primeras letras y elimina muchas palabras que no coinciden. Si realmente encuentras ese cuadrado, verifica si se pueden hacer con esas piezas.

Para cuadrados de 5x5: después de pensar un poco, no puede ser peor que O (12000!/11990!) Para palabras de texto aleatorias. Pero pensándolo un poco más. Cada vez que arreglas una carta (en texto normal), eliminas aproximadamente el 90% (una suposición optimista) de tus palabras. Esto significa que después de tres iteraciones tienes 12 palabras. Entonces la velocidad real sería

O(n * n/10 * n/10 * n/100 * n/100 * n/1000 * n/1000 ... 
which for 12000 elements acts something like n^4 algorithm 

que no es tan malo.

Probablemente alguien pueda hacer un mejor análisis del problema. Pero la búsqueda de palabras aún debe converger bastante rápido.

Puede haber más eliminaciones al abusar de las letras poco frecuentes. Básicamente encuentra todas las palabras que tienen letras poco frecuentes. Intenta hacer una posición correspondiente para cada letra. Construya un conjunto de letras válidas para cada posición.

Por ejemplo, supongamos que tenemos cuatro palabras con la letra Q en ella.

AQFED, ZQABE, EDQDE, ELQUO 

this means there are two valid positionings of those: 

xZxxx 
AQFED 
xAxxx ---> this limits our search for words that contain [ABDEFZ] as the second letter 
xBxxx 
xExxx 

same for the other 

EDQDE ---> this limits our search for words that contain [EDLU] as the third letter 
ELQUO 

all appropriate words are in union of those two conditions 

Así que, básicamente, si tenemos varias palabras que contienen la letra X infrecuente en el canal S en la posición N, significa que otras palabras que están en esa matriz deben tener carta que también está en S en la posición n.

Fórmula:

• Encuentra todas las palabras que contienen poco frecuentes letra X en la posición 1 (siguiente iteración 2, 3 ...)
• Hacer un conjunto A de las letras en esas palabras
• mantener sólo las palabras del diccionario que tienen carta del conjunto a en la posición 1
• tratar de encajar los en la matriz (con el primer método)
• Repita con la posición 2

Answer 4

Aquí hay muchos 5x5 precalculados. Deja como ejercicio para el lector para encontrar los compatibles 4 :-)

http://www.gtoal.com/wordgames/wordsquare/all5

Answer 5

estoy empezando con algo más simple.

Éstos son algunos resultados hasta el momento:

3736 2x2 solutions 
8812672 3x3 solutions 

The 1000th 4x4 solution is 
    A A H S 
    A C A I 
    L A I R 
    S I R E 

The 1000th 5x5 solution is 
    A A H E D 
    A B U N A 
    H U R S T 
    E N S U E 
    D A T E D 

The 1000th 2x4x4 solution is 
    A A H S | A A H S 
    A B A C | A B A C 
    H A I R | L E K U 
    S C R Y | S T E D 
    --------+-------- 
    D E E D | D E E M 
    E I N E | I N T I 
    E N O L | O V E R 
    T E L T | L Y N E 

Tenga en cuenta que la transposición de una 'A' y un espacio en blanco que se utiliza como una 'A' debe considerarse la misma solución. Pero la transposición de las filas con las columnas se debe considerar como una solución diferente. Espero que tenga sentido.