拼字游戏瓷砖检查
拼字检查瓷砖，你做四个5×5的字母总共100个瓷砖。 我想做一个所有40个水平和垂直的单词是有效的。 可用拼贴的集合包含：
- 12×E
- 9 x A，I
- 8 x O
- 6×N，R，T
- 4 x D，L，S，U
- 3 x G
- 2×B，C，F，H，M，P，V，W，Y，空白瓦（通配符）
- 1×K，J，Q，X，Z
有效单词字典在这里可以find （700KB）。 大约有12000个有效的5个字母的单词。
下面是一个例子，其中所有20个水平字都是有效的：
ZOWIE|PINOT YOGIN|OC t AD <= blank being used as 't' XEBEC|NALED WAITE|MERLE VINER|LUTEA ---------+--------- USNEA|KNOSP TAVER|JOLED SOFTA|IAMBI RIDGY|HAIT h <= blank being used as 'h' QURSH|GROUF 我想创build一个所有的垂直的也是有效的。 你能帮我解决吗？ 这不是功课。 这是一个朋友问我帮忙的问题。
最终编辑： 解决！ 这是一个解决scheme。
GNAWN|jOULE RACHE|EUROS IDIOT|STEAN PINOT|TRAvE TRIPY|SOLES -----+----- HOWFF|ZEBRA AGILE|EQUID CIVIL|BUXOM EVENT|RIOJA KEDGY|ADMAN
这里是我的拼字游戏构build的照片。 http://twitpic.com/3wn7iu
一旦我有正确的方法，这个很容易find，所以我敢打赌，你可以find更多的方式。 请参阅下面的方法。
从每个行和列的5个字母词典的字典中构造一个前缀树。 recursion地，给定的贴图位置是有效的，如果它为其列和行形成有效的前缀，并且如果该贴图可用，并且下一个贴图位置是有效的。 基本情况是，如果没有剩下的图块，它是有效的。
如Glenn所说，find所有有效的5×5电路板可能是有意义的，并且看看是否有四个电路板可以组合。 recursion到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开始的电路板之前陷入困境。 在看到有多less个5×5的块之后，我修改了代码来列出所有有效的5×5块。 我现在有一个150 MB的文本文件，所有的4,430,974 5×5解决scheme。
我也尝试了通过完整的100个瓷砖recursion，而且还在运行。
编辑2：这里是我生成的所有有效的5×5块的列表。 http://web.cs.sunyit.edu/~levyt/solutions.rar
编辑3：嗯，似乎有我的瓷砖使用情况跟踪中的一个错误，因为我刚刚在我的输出文件中find一个使用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; }
在找出有多less块（还有数十亿块）之后，我转而试图寻找某些types的块，特别是使用罕见字母难以构build的块。 我的希望是，如果我最后得到了一组足够的信件进入最后一个块，那么有效块的广阔空间可能会有一个字母组。
我给每个tile分配一个与它出现的5个字母单词数量成反比的值。然后，当我find一个有效的block时，我总结了tile的值，如果分数是我看过的最好的，我会打印出去块。
对于第一块我删除了空白的瓷砖，确定最后一块最需要的灵活性。 让它运行，直到我没有看到一个更好的块出现了一段时间，我select了最好的块，并从袋子中取出瓷砖，并再次运行程序，得到第二个块。 我重复了这个第三块。 然后对于最后一个块，我添加了空白，并使用它find的第一个有效的块。
这是我将如何尝试这个。 首先构造一个前缀树。
选一个字，并将其水平放置在顶部。 select一个词并垂直放置。 交替他们，直到用尽选项。 交替你开始修复的第一个字母，并消除大量的不匹配的话。 如果你确实find了这样的方块，那就去检查一下是否可以用这些方块做出来。
对于5×5的方格：做一些思考之后，对于随机文本单词来说，不能比O（12000！/ 11990！）差。 但多想一点。 每当你修改一个字母（用正常的文字），你就会消除90％左右（乐观的猜测）。 这意味着三次迭代后，你有12个字。 所以实际的速度会是
O(n * n/10 * n/10 * n/100 * n/100 * n/1000 * n/1000 ... which for 12000 elements acts something like n^4 algorithm
这并不坏。
也许有人可以更好地分析这个问题。 但是search文字应该仍然很快收敛。
滥用罕见字母可以消除更多。 基本上find所有有不经常的字母的单词。 尝试为每个字母做一个匹配的位置。 为每个位置构build一组有效的字母。
例如，假设我们有四个字母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
所以基本上，如果在位置N的单词S中有多个包含不常用字母X的单词，则意味着该单元中的其他单词必须在位置n上具有也在S中的字母。
式：
- 查找包含位置1处偶发字母X的所有单词（下一次迭代2,3 …）
- 用这些字母中的字母来表示一个集合A.
- 只保留字典中来自位置1的集合A的字母的单词
- 尝试将其纳入matrix（使用第一种方法）
- 重复位置2
我会以悲观的眼光来看待这个问题（天真地说，肯定）。 我试图certificate没有5×5解决scheme，因此当然不是四个 5×5解决scheme。 为了certificate没有5×5解决scheme，我试图从所有可能性构build一个。 如果我的猜想失败了，那么我就可以构build一个5×5的解决scheme，那么，我就有办法构build5x5的解决scheme，我会尝试构build所有的（独立的）5×5解决scheme。 如果至less有4个，那么我会确定一些组合是否符合字母数量的限制。
[编辑]空集已经确定有“4,430,974 5×5解决scheme”。 这些有效吗？ 我的意思是，我们可以使用的字母数量有限制。 这个限制可以表示为对应于A，B，C等限制的边界向量BV = [9,2,2,4，…]（你可以在空集的代码中看到这个向量）。 如果字母计数向量的每个项小于BV中的相应项，则5×5解决scheme是有效的。 如果5×5解决scheme在创build时是有效的，那将很容易。 也许4,430,974的数字可以减less，比如说N.
不pipe怎么说，我们可以把这个问题说成是：find总和等于BV的N中的四个字母计数向量。 有（N，4）个可能的和（“N choose 4”）。 N等于400万，这仍然是10 ^ 25的数量级 – 不是一个令人鼓舞的数字。 也许你可以search四个第一项总和为9，如果是这样检查他们的第二项总和为2等
我会说，从N中select4后，计算是独立的，所以如果你有一个多核机器，你可以通过一个并行解决scheme使它更快。
平行化可能不会有太大的区别。 在这一点上，我可能乐观地认为：肯定会有比我预期更多的5×5解决scheme，所以最终的解决scheme可能比预期的要多。 也许你可能不必深入到10 ^ 25打一个。
我从简单的事情开始。
以下是目前为止的一些结果：
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
请注意，将“A”和用作“A”的空白转换为同一个解决scheme。 但是将列与行进行转置应该被认为是不同的解决scheme。 我希望这是有道理的。
这里有很多预先计算好的5×5的。 作为练习留给读者find4个兼容的:-)
