对于拼字游戏中的图块检查，您可以制作四个5x5的字母网格，总计100个图块。我想在其中40个水平和垂直单词都有效的地方做一个。可用磁贴的集合包含：
有效词词典在此处可用（700KB）。大约有12,000个有效的5个字母词。
这是一个示例，其中所有20个水平词均有效：
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
我想创建一个所有垂直元素都有效的元素。你能帮我解决这个问题吗？这不是功课。这是一个朋友向我寻求帮助的问题。
Final Edit: Solved! Here is a solution.
GNAWN|jOULE RACHE|EUROS IDIOT|STEAN PINOT|TRAvE TRIPY|SOLES -----+----- HOWFF|ZEBRA AGILE|EQUID CIVIL|BUXOM EVENT|RIOJA KEDGY|ADMAN
这是用我的拼字游戏制作的照片。http://twitpic.com/3wn7iu
一旦采用正确的方法，就很容易找到这个，所以我敢打赌，您可以通过这种方式找到更多。方法请参见下文。
从每行和每列5个字母单词的字典构造一个前缀树。递归地，如果给定的图块放置为其列和行形成有效的前缀，并且该图块可用，并且下一个图块放置有效，则该放置有效。基本情况是，如果没有要放置的图块，则是有效的。
就像Glenn所说的那样，找到所有有效的5x5板可能很有意义，然后看看是否可以将其中的四个组合在一起。递归到100的深度听起来并不有趣。
编辑：这是我的代码的版本2。
#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; }
这将首先尝试不常用的字母，但我不确定这是一个好主意。它开始陷入困境，然后才 以x开头退出董事会。在看到有多少5x5块之后，我更改了代码以仅列出所有有效的5x5块。我现在有一个150 MB的文本文件，其中包含所有4,430,974 5x5解决方案。
我还尝试了整个100个磁贴的递归操作，并且仍在运行。
编辑2：这是我生成的所有有效5x5块的列表。http://web.cs.sunyit.edu/~levyt/solutions.rar
编辑3：嗯，我的图块使用情况跟踪中似乎有一个错误，因为我刚刚在我的输出文件中找到了一个使用5 Z的块。
COSTE ORCIN SCUZZ TIZZY ENZYM
编辑4：这是最终产品。
#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; }
在找到了多少个区块（将近20亿并且仍在计数）之后，我转而尝试查找某些类型的区块，尤其是难以使用不常见的字母构造的区块。我的希望是，如果我最后得到了足够良性的字母集进入最后一个块，那么有效块的巨大空间可能会对那组字母有一个字母。
我给每个图块分配一个与它出现的5个字母单词数量成反比的值。然后，当我找到一个有效的块时，我将对图块值进行求和，如果分数是我所见过的最好，我将打印出块。
对于第一个块，我删除了空白磁贴，确定最后一个块最需要这种灵活性。在让它运行直到一段时间没有看到更好的块之后，我选择了最佳块，然后从袋子中取出其中的砖块，然后再次运行程序，得到第二个块。我在第三段重复了这个步骤。然后，对于最后一个块，我重新添加了空格，并使用了找到的第一个有效块。
