拼字游戏拼图检查

Question

对于在拼字游戏中检查拼贴，您将制作四个5x5的字母格子，共100个拼图。我想做一个所有40个水平和垂直单词都有效的单词。所述一组可用瓦片包含：

• 12×ë
• 9×A，I
• 8×○
• 6×N，R，T
• 4×d，L，S ，U
• 3×g下
• 2×B，C，F，H，M，P，V，W，Y，空块（通配符）
• 1×K，J，Q，X，Z

有效字词典有效here（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 

我想创建一个所有垂直的人也有效。你能帮我解决这个问题吗？这不是作业。这是一个朋友问我寻求帮助的问题。

Answer 1

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

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个字母单词构造一个前缀树。递归地，如果给定的贴图位置为其列和行形成有效的前缀，并且该贴图可用并且下一个贴图位置有效，那么给定的贴图位置是有效的。基本情况是，如果没有可放置的图块，它是有效的。

它可能是有意义的只是找到所有有效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的块列表。编辑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; 
} 

找出多少块有（近2十亿仍然算起）之后，我切换到试图找到某种类型的块，特别是难以构建使用罕见的信件的人。我的希望是，如果我最终得到一组足够的信件进入最后一个块，那么有效块的广阔空间可能会有一个字母组合。

我给每个tile分配一个与它出现的5个字母单词数量成反比的值。然后，当我找到一个有效的块时，我总结这些tile值，如果分数是我看过的最好的，我会打印出该块。

对于第一块我删除了空块，盘算最后一块需要这种灵活性最。让它运行直到我没有看到一段时间内出现更好的块，我选择了最好的块，然后从包中取出块并再次运行程序，得到第二块。我重复了这个第三块。然后，为最后一个块添加空白，并使用它找到的第一个有效块。

Answer 2

我会通过采取悲观的看法来解决这个问题（天真，可以肯定）。我试图证明没有5x5解决方案，因此肯定不是四个 5x5解决方案。为了证明没有5x5解决方案，我会尝试从所有可能性构建一个解决方案。如果我的猜想失败了，并且我能够构建一个5x5的解决方案，那么，我有办法构建5x5的解决方案，我会尝试构建（独立的）5x5解决方案的所有。如果至少有4个，那么我会确定某个组合是否符合字母数量限制。

[编辑] Null Set已确定存在“4,430,974 5x5解决方案”。这些有效吗？ 我的意思是我们对可以使用的字母数量有限制。这个限制可以表示为对应于A，B，C等限制的边界向量BV = [9,2,2,4，...]（你可以在空集的代码中看到这个向量）。如果字母计数向量的每个项小于BV中的对应项，则5x5解决方案有效。如果5x5解决方案在创建时是有效的，那将很容易。也许4,430,974的数字可以减少，比如说N。

无论如何，我们可以说这个问题是这样的：在总和等于BV的N中找到四个字母计数向量。有（N，4）个可能的总和（“N选择4”）。 N等于400万，这仍然是10^25的数量级 - 不是一个令人鼓舞的数字。也许你可以搜索四个第一项总和为9，如果是这样检查他们的第二项总和为2等。

我要说，从N选择4后，计算是独立的，所以如果你有多核机器，您可以通过并行解决方案实现更快的速度。虽然并行化可能不会有太大的区别。在这一点上，我可能会乐观地认为：肯定会有比我预期更多的5x5解决方案，因此最终的解决方案可能比预期的要多。也许你可能不必深入10^25打一个。

Answer 3

下面是我想尝试这个。首先构造一个前缀树。

选择一个单词和水平放置在上面。选择一个词并垂直放置。交替他们，直到用尽选项。通过交替你开始修复第一个字母，并消除大量不匹配的单词。如果你确实找到了这样的方块，那么请检查它们是否可以用这些方块制作。

对于5x5的方格：做一些思考后，它不能为O更糟随机文本字（一万一千九百九分之一万二！）。但多想一点。每当你修改一封信（用正常的文字），你就会消除你的话的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 

这并不坏。

也许有人可以做的问题，更好地分析。但是搜索词语仍然应该很快收敛。

可以有更消除了滥用罕见的字母来完成。基本上找到所有字母不频繁的单词。尝试为每个字母做一个匹配的位置。为每个位置构建一组有效的字母。

例如，假设我们有四个词与它字母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 

因此，基本上，如果我们有包含在字S不频繁的字母X在位置N多个词，意味着换句话说是在矩阵必须具有字母，这也是处于S在位置n。

公式：

• 查找包含罕见的字母X在位置1的所有单词（下一次迭代2，3 ...）
• 制定一套A掉字母的那些话
• 只保留从词典具有从集合A字母在位置1
• 尝试那些词，以适应那些到基质（与第一种方法）
• 重复与位置2

Answer 4

这里有大量的预先计算的5×5的。作为练习留给读者去发现4周兼容的人:-)

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

Answer 5

我开始用简单的东西。

下面是到目前为止的一些结果：

3736 2x2 solutions 
8812672 3x3 solutions 

The 1000th 4x4 solution is 
    A A H S 
    A C A I 
    L A I R 
    S I R E 

The 1000th 5x5 solution is 
    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 

The 1000th 2x4x4 solution is 
    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 

注意，转置的“A”和正被用作“A”空白应该被认为是相同的解决方案。但是将列与行进行转置应该被认为是不同的解决方案。我希望这是有道理的。