Vérification des carreaux Scrabble

Final Edit: 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 construite avec mon jeu de scrabble. http://twitpic.com/3wn7iu

Celui-ci était facile à trouver une fois que j’ai eu la bonne approche, alors je parie que vous pourriez en trouver beaucoup plus de cette façon. Voir ci-dessous pour la méthodologie.

Construisez une arborescence de préfixes à partir du dictionnaire de 5 mots pour chaque ligne et colonne. Récursivement, un emplacement de mosaïque donné est valide s’il forme des préfixes valides pour sa colonne et sa ligne, et si la mosaïque est disponible, et si le placement de mosaïque suivant est valide. Le cas de base est qu’il est valide s’il n’y a pas de tuile à placer.

Il est probablement logique de trouver toutes les cartes 5×5 valides, comme l’a dit Glenn, et de voir si quatre d’entre elles peuvent être combinées. Récurer à une profondeur de 100 ne semble pas amusant.

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

 #include  #include  #include  #include  typedef union node node; union node { node* child[26]; char ssortingng[6]; }; typedef struct snap snap; struct snap { node* rows[5]; node* cols[5]; char tiles[27]; snap* next; }; node* root; node* vsortinge[5]; node* hsortinge[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* ssortingng){ node* place = root; int i; for(i=0;i<5;i++){ if(place->child[ssortingng[i] - 'A'] == NULL){ int j; place->child[ssortingng[i] - 'A'] = malloc(sizeof(node)); for(j=0;j<26;j++){ place->child[ssortingng[i] - 'A']->child[j] = NULL; } } place = place->child[ssortingng[i] - 'A']; } memcpy(place->ssortingng, ssortingng, 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]->ssortingng); } printf("\n"); for(i=0;i<5;i++){ printf("%s\n", b->rows[i]->ssortingng); } printf("\n"); for(i=0;i<5;i++){ printf("%s\n", c->rows[i]->ssortingng); } printf("\n"); for(i=0;i<5;i++){ printf("%s\n", d->rows[i]->ssortingng); } exit(0); } } } } } void snapshot(){ snap* shot = malloc(sizeof(snap)); int i; for(i=0;i<5;i++){ printf("%s\n", htrie[i]->ssortingng); shot->rows[i] = hsortinge[i]; shot->cols[i] = vsortinge[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 = vsortinge[x]; node* oldh = hsortinge[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 && hsortinge[y]->child[order[i]]!=NULL && (tile = bag[i] ? i : bag[26] ? 26 : -1) + 1) { vsortinge[x] = vsortinge[x]->child[order[i]]; hsortinge[y] = hsortinge[y]->child[order[i]]; bag[tile]--; pick(nextx, nexty); vsortinge[x] = oldv; hsortinge[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; } 

Cela essaie d'abord les lettres peu fréquentes, ce dont je ne suis plus sûr, c'est une bonne idée. Il commence à s'enliser avant de sortir des tableaux en 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 avec 4 430 974 solutions 5x5.

Je l'ai également essayé avec juste récurer à travers les 100 tuiles complètes, 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 y avoir un bogue 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  #include  #include  #include  typedef union node node; union node { node* child[26]; char ssortingng[6]; }; node* root; node* vsortinge[5]; node* hsortinge[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* ssortingng){ node* place = root; int i; for(i=0;i<5;i++){ if(place->child[ssortingng[i] - 'A'] == NULL){ int j; place->child[ssortingng[i] - 'A'] = malloc(sizeof(node)); for(j=0;j<26;j++){ place->child[ssortingng[i] - 'A']->child[j] = NULL; } } place = place->child[ssortingng[i] - 'A']; } memcpy(place->ssortingng, ssortingng, 6); } void snapshot(){ static int count = 0; int i; for(i=0;i<5;i++){ printf("%s\n", htrie[i]->ssortingng); } 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 = vsortinge[x]; node* oldh = hsortinge[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 && hsortinge[y]->child[order[i]]!=NULL && (tile = bag[order[i]] ? order[i] : bag[26] ? 26 : -1) + 1) { vsortinge[x] = vsortinge[x]->child[order[i]]; hsortinge[y] = hsortinge[y]->child[order[i]]; bag[tile]--; score+=value[tile]; pick(nextx, nexty); vsortinge[x] = oldv; hsortinge[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 train de compter), je suis passé à la recherche de certains types de blocs, en particulier ceux difficiles à construire avec des lettres peu communes. J'espérais que si je me retrouvais avec un ensemble de lettres suffisamment bénin pour entrer dans le dernier bloc, le vaste espace de blocs valides en aurait probablement un pour cet ensemble de lettres.

J'ai assigné à chaque tuile une valeur inversement proportionnelle au nombre de mots de 5 lettres dans lesquels elle apparaît. Puis, quand j'ai trouvé un bloc valide, je résumerais les valeurs des tuiles et si la partition était la meilleure que j'avais vue, j'imprimerais sortir du bloc.

Pour le premier bloc, j'ai enlevé les tuiles vides, pensant que le dernier bloc aurait le plus besoin de cette flexibilité. Après l'avoir laissé courir jusqu'à ce que je n'aie plus vu un meilleur bloc pendant un certain temps, j'ai sélectionné le meilleur bloc et j'ai retiré les tuiles du sac, puis j'ai exécuté à nouveau le programme pour obtenir le deuxième bloc. Je l'ai répété pour le 3ème bloc. Ensuite, pour le dernier bloc, j'ai ajouté les blancs et utilisé le premier bloc valide trouvé.

Voici comment j’essaierais ceci. Construisez d’abord un arbre de préfixe.

Choisissez un mot et placez-le horizontalement sur le dessus. Choisissez un mot et placez-le verticalement. Alternez-les jusqu’à épuisement des options. En alternant, vous commencez à corriger les premières lettres et à éliminer beaucoup de mots qui ne correspondent pas. Si vous trouvez vraiment un tel carré, alors vérifiez si elles peuvent être faites avec ces pièces.

Pour les carrés 5×5: après avoir pensé que cela ne peut pas être pire que O (12000! / 11990!) Pour des mots de texte aléatoires. Mais y penser un peu plus. Chaque fois que vous corrigez une lettre (en texte normal), vous éliminez environ 90% (une hypothèse 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 ... which for 12000 elements acts something like n^4 algorithm 

ce qui n’est pas si mal

Probablement quelqu’un peut faire une meilleure parsing du problème. Mais la recherche de mots devrait encore converger assez rapidement.

Il peut y avoir plus d’élimination en abusant des lettres peu fréquentes. Essentiellement trouver tous les mots qui ont des lettres peu fréquentes. Essayez de faire des positions correspondantes pour chaque lettre. Construisez un ensemble de lettres valides pour chaque position.

Par exemple, supposons que nous ayons quatre mots avec la lettre Q.

  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 

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

Formule:

• Trouver tous les mots qui contiennent une lettre peu fréquente X à la position 1 (prochaine itération 2, 3 …)
• Faire un ensemble A des lettres dans ces mots
• Ne conservez que les mots du dictionnaire qui ont une lettre de l’ensemble A en position 1
• Essayez de les adapter à la masortingce (avec la première méthode)
• Répétez avec la position 2

Je voudrais aborder le problème (naïvement, bien sûr) en adoptant un sharepoint vue pessimiste. J’essayerais de prouver qu’il n’y avait pas de solution 5×5, et donc certainement pas quatre solutions 5×5. Pour prouver qu’il n’y avait pas de solution 5×5, j’essayerais d’en construire une de toutes les possibilités. Si ma conjecture échouait et que je pouvais construire une solution 5×5, eh bien, j’aurais un moyen de construire des solutions 5×5 et j’essaierais de construire toutes les solutions 5×5 (indépendantes). S’il y en avait au moins 4, je déterminerais si une combinaison répondait aux ressortingctions du nombre de lettres.

[Edit] Null Set a déterminé qu’il existe “4 430 974 5×5 solutions”. Sont-ils valables? Je veux dire que nous avons une limitation du nombre de lettres que nous pouvons utiliser. Cette limitation peut être exprimée comme 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 5×5 est valide si chaque terme de son vecteur de comptage de lettres est inférieur au terme correspondant dans BV. Il serait facile de vérifier si une solution 5×5 est valide telle qu’elle a été créée. Peut-être que le nombre de 4.430.974 peut être réduit, disons à N.

Quoi qu’il en soit, nous pouvons poser le problème comme suit: trouver quatre vecteurs de comptage de lettres parmi les N dont la sum est égale à BV. Il y a (N, 4) sums possibles (“N choisir 4”). Avec N égal à 4 millions, ce chiffre est encore de l’ordre de 10 ^ 25, ce qui n’est pas encourageant. Peut-être pourriez-vous en chercher quatre dont les premiers termes totalisent 9 et vérifier si leurs deuxièmes termes correspondent à 2, etc.

Je ferais remarquer qu’après avoir choisi 4 de N, les calculs sont indépendants, donc si vous avez une machine multi-core, vous pouvez rendre cela plus rapide avec une solution parallèle.

[Edit2] La parallélisation ne ferait probablement pas beaucoup de différence, cependant. À ce stade, je suis peut-être optimiste: il y a certainement plus de solutions 5×5 que prévu, il peut donc y avoir plus de solutions finales que prévu. Peut-être n’auriez-vous pas à aller loin dans le 10 ^ 25 pour en atteindre un.

Je commence par quelque chose de plus simple.

Voici quelques résultats à ce jour:

  3736 2x2 solutions 8812672 3x3 solutions The 1000th 4x4 solution is AAHS ACAI LAIR SIRE The 1000th 5x5 solution is AAHED ABUNA HURST ENSUE DATED The 1000th 2x4x4 solution is AAHS | AAHS ABAC | ABAC HAIR | LEKU SCRY | STED --------+-------- DEED | DEEM EINE | INTI ENOL | OVER TELT | LYNE 

Notez que la transposition d’un «A» et d’un blanc utilisé comme «A» doit être considérée comme la même solution. Mais la transposition des lignes avec les colonnes doit être considérée comme une solution différente. J’espère que cela à du sens.

Voici beaucoup de 5×5 pré-calculés. Laissé comme exercice au lecteur pour trouver 4 compatibles 🙂

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