Vérification de la tuile Scrabble

Question

Pour vérifier les mots au Scrabble, vous créez quatre grilles de lettres 5x5 totalisant 100 tuiles. J'aimerais en créer une où les 40 mots horizontaux et verticaux sont tous valides. L'ensemble des tuiles disponibles contient :

• 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, tuile blanche (joker)
• 1 x K, J, Q, X, Z

Le dictionnaire des mots valides est disponible ici (700 Ko). Il y a environ 12 000 mots valides de 5 lettres.

Voici un exemple où les 20 mots horizontaux sont tous valides :

Z O W I E|P I N O T
Y O G I N|O C t A D   <= le joker est utilisé comme '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   <= le joker est utilisé comme 'h'
Q U R S H|G R O U F

J'aimerais en créer une où les mots verticaux sont également tous valides. Pouvez-vous m'aider à résoudre cela ? Ce n'est pas un devoir. C'est une question pour laquelle un ami m'a demandé de l'aide.

Answer 1

Montage final : Résolu ! Voici une solution.

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

Voici une photo de sa construction avec mon jeu de scrabble. http://twitpic.com/3wn7iu

Celui-ci a été facile à trouver une fois que j'ai eu la bonne approche, donc je parie que vous pourriez en trouver beaucoup d'autres de cette façon. Voir ci-dessous pour la méthodologie.

---

Construire un arbre de préfixes à partir du dictionnaire des mots de 5 lettres pour chaque ligne et chaque colonne. De manière récursive, un placement de tuile donné est valide s'il forme des préfixes valides pour sa colonne et sa ligne, et si la tuile est disponible, et si le placement de tuile suivant est valide. Dans le cas de base, il est valide s'il n'y a plus de tuile à placer.

Il est probablement judicieux de trouver toutes les planches 5x5 valides, comme Glenn l'a dit, et de voir si quatre d'entre elles peuvent être combinées. Recourir à une profondeur de 100 n'a pas l'air amusant.

Edit : Voici la version 2 de mon code pour cela.

#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;
}

Il essaie d'abord les lettres peu fréquentes, ce qui n'est plus une bonne idée. Il commence à s'embourber avant d'arriver à sortir des tableaux commençant par x. Après avoir vu combien de blocs 5x5 il y avait, j'ai modifié le code pour simplement lister tous les blocs 5x5 valides. J'ai maintenant un fichier texte de 150 Mo contenant les 4 430 974 solutions 5x5.

J'ai également essayé avec une récurrence de 100 tuiles, et cela fonctionne toujours.

Edit 2 : Voici la liste de tous les blocs 5x5 valides que j'ai générés. http://web.cs.sunyit.edu/~levyt/solutions.rar

Edit 3 : Hmm, il semble qu'il y avait un bug dans mon suivi de l'utilisation des tuiles, car je viens de trouver un bloc dans mon fichier de sortie qui utilise 5 Zs.

COSTE
ORCIN
SCUZZ
TIZZY
ENZYM

Edit 4 : Voici le produit 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;
}

Après avoir découvert combien de blocs il y avait (près de 2 milliards et toujours en cours de calcul), je me suis mis à essayer de trouver certains types de blocs, en particulier ceux qui sont difficiles à construire et qui utilisent des lettres peu communes. J'espérais que si je me retrouvais avec un ensemble de lettres assez bénin pour le dernier bloc, le vaste espace de blocs valides en contiendrait probablement un pour cet ensemble de lettres.

J'ai attribué à chaque carreau une valeur inversement proportionnelle au nombre de mots de 5 lettres dans lesquels il apparaît. Ensuite, lorsque je trouvais un bloc valide, j'additionnais les valeurs des tuiles, et si le score était le meilleur que j'avais vu jusqu'alors, j'imprimais le bloc.

Pour le premier bloc, j'ai enlevé les tuiles vierges, pensant que le dernier bloc aurait le plus besoin de cette flexibilité. Après l'avoir laissé tourner jusqu'à ce que je n'aie pas vu apparaître un meilleur bloc pendant un certain temps, j'ai sélectionné le meilleur bloc, j'ai retiré les tuiles qu'il contenait du sac et j'ai relancé le programme, obtenant ainsi le deuxième bloc. J'ai répété cela pour le troisième bloc. Puis, pour le dernier bloc, j'ai rajouté les tuiles vides et utilisé le premier bloc valide qu'il a trouvé.

Answer 2

Je aborderais le problème (naïvement, c'est sûr) en adoptant un point de vue pessimiste. J'essaierais de prouver qu'il n'y a pas de solution 5x5, et donc certainement pas quatre solutions 5x5. Pour prouver qu'il n'y a pas de solution 5x5, j'essaierais d'en construire une à partir de toutes les possibilités. Si ma conjecture échouait et que je parvenais à construire une solution 5x5, eh bien, alors, je aurais un moyen de construire des solutions 5x5 et j'essaierais de construire toutes les solutions 5x5 (indépendantes). S'il y en avait au moins 4, alors je déterminerais si une combinaison satisfait aux restrictions du nombre de lettres.

[Edit] Null Set a déterminé qu'il y a "4,430,974 solutions 5x5". Sont-elles valides? Je veux dire que nous avons une limitation sur le nombre de lettres que nous pouvons utiliser. Cette limitation peut être exprimée sous la forme d'un vecteur de limites BV = [9, 2, 2, 4, ...] correspondant aux limites sur A, B, C, etc. (Vous voyez ce vecteur dans le code de Null Set). Une solution 5x5 est valide si chaque élément de son vecteur de décompte de lettres est inférieur à l'élément correspondant de BV. Il serait facile de vérifier si une solution 5x5 est valide car elle a été créée. Peut-être que le nombre 4,430,974 peut être réduit, disons à N.

Quoi qu'il en soit, nous pouvons formuler le problème comme suit : trouver quatre vecteurs de décompte de lettres parmi les N dont la somme est égale à BV. Il existe (N, 4) sommes possibles ("N choisit 4"). Avec N égal à 4 millions, cela reste de l'ordre de 10^25---pas un nombre encourageant. Peut-être pourriez-vous rechercher quatre dont les premiers termes somment à 9, puis vérifier que leurs deuxièmes termes somment à 2, etc.

Je noterais qu'après avoir choisi 4 parmi N, les calculs sont indépendants, donc si vous avez une machine multicœur, vous pouvez accélérer le processus avec une solution parallèle.

[Edit2] La parallélisation ne ferait probablement pas beaucoup de différence, cependant. À ce stade, je pourrais adopter un point de vue optimiste : il y a certainement plus de solutions 5x5 que je ne pensais, donc il peut y avoir plus de solutions finales que prévu, également. Peut-être que vous n'aurez pas à vous aventurer loin dans le 10^25 pour en trouver une.

Answer 3

Voici comment je vais essayer ceci. Tout d'abord, construisez un arbre de préfixes.

Prenez un mot et placez-le horizontalement en haut. Prenez un mot et placez-le verticalement. Alternez-les jusqu'à épuisement des options. En alternant, vous commencez à fixer les premières lettres et à éliminer de nombreux mots qui ne correspondent pas. Si vous trouvez vraiment un tel carré, vérifiez ensuite s'ils peuvent être fabriqués avec ces pièces.

Pour les carrés 5x5 : après avoir réfléchi un peu, cela ne peut pas être pire que O(12000!/11990!) pour des mots de texte aléatoires. Mais en y réfléchissant un peu plus. Chaque fois que vous fixez une lettre (dans un texte normal) vous éliminez environ 90% (une supposition optimiste) de vos mots. Cela signifie qu'après trois itérations, vous avez 12 mots. Donc la vitesse réelle serait

O(n * n/10 * n/10 * n/100 * n/100 * n/1000 * n/1000 ...
ce qui pour 12000 éléments agit un peu comme un algorithme n^4

ce qui n'est pas si mal.

Probablement que quelqu'un pourrait faire une meilleure analyse du problème. Mais la recherche de mots devrait quand même converger assez rapidement.

Il est possible d'éliminer davantage en abusant des lettres peu fréquentes. Trouvez essentiellement tous les mots qui contiennent des lettres peu fréquentes. Essayez de trouver des positions correspondantes pour chaque lettre. Construisez un ensemble de lettres valides pour chaque position.

Par exemple, disons que nous avons quatre mots avec la lettre Q dedans.

 AQFED, ZQABE, EDQDE, ELQUO

 cela signifie qu'il y a deux positionnements valides de ces derniers :

 xZxxx
 AQFED
 xAxxx   ---> cela limite notre recherche de mots contenant [ABDEFZ] comme deuxième lettre
 xBxxx
 xExxx

 pareil pour l'autre

 EDQDE   ---> cela limite notre recherche de mots contenant [EDLU] comme troisième lettre
 ELQUO

 tous les mots appropriés sont dans l'union de ces deux conditions

Donc fondamentalement, si nous avons plusieurs mots qui contiennent la lettre peu fréquente X dans le mot S à la position N, cela signifie que les autres mots qui se trouvent dans cette matrice doivent également avoir une lettre qui est également dans S à la position n.

Formule :

• Trouvez tous les mots qui contiennent la lettre peu fréquente X à la position 1 (puis itération 2, 3...)
• Créez un ensemble A avec les lettres de ces mots
• Ne gardez que les mots du dictionnaire qui ont une lettre de l'ensemble A à la position 1
• Essayez de les adapter à la matrice (avec la première méthode)
• Répétez avec la position 2

Answer 4

Je commence par quelque chose de plus simple.

Voici quelques résultats jusqu'à présent :

   3736 solutions 2x2
8812672 solutions 3x3

La 1000ème solution 4x4 est
   A A H S
   A C A I
   L A I R
   S I R E

La 1000ème solution 5x5 est
   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

La 1000ème solution 2x4x4 est
   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

Remarquez que transposer un 'A' et un espace qui est utilisé comme un 'A' devrait être considéré comme la même solution. Mais transposer les lignes avec les colonnes devrait être considéré comme une solution différente. J'espère que cela a du sens.

Answer 5

Voici beaucoup de carrés de 5x5 précalculés. Laissez à l'exercice au lecteur de trouver 4 compatibles :-)

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