拼字游戏检查

最终编辑： 解决！ 这是一个解决方案。

GNAWN|jOULERACHE|EUROSIDIOT|STEANPINOT|TRAvETRIPY|SOLES-----+-----HOWFF|ZEBRAAGILE|EQUIDCIVIL|BUXOMEVENT|RIOJAKEDGY|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!nn");         for(i=0;i<5;i++){  printf("%sn", a->rows[i]->string);         }         printf("n");         for(i=0;i<5;i++){  printf("%sn", b->rows[i]->string);         }         printf("n");         for(i=0;i<5;i++){  printf("%sn", c->rows[i]->string);         }         printf("n");         for(i=0;i<5;i++){  printf("%sn", d->rows[i]->string);         }         exit(0);     } }        }    }}void snapshot(){    snap* shot = malloc(sizeof(snap));    int i;    for(i=0;i<5;i++){        printf("%sn", 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的输出文件中找到了一个块。

COSTEORCINSCUZZTIZZYENZYM

编辑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 ADMANchar 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 KEDGYchar 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 SOLESchar 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("%sn", 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个字母单词数量成反比的值。然后，当我找到一个有效的块时，我将对图块值进行求和，如果分数是我所见过的最好，我将打印出块。

对于第一个块，我删除了空白磁贴，确定最后一个块最需要这种灵活性。在让它运行直到一段时间没看到更好的块之后，我选择了最佳块，然后从袋子中取出其中的砖块，然后再次运行程序，得到第二个块。我在第三段重复了这个步骤。然后，对于最后一个块，我重新添加了空格，并使用了找到的第一个有效块。