拼字砖检查 [英] Scrabble tile checking
问题描述
对于拼贴检查，您可以制作四个5x5格的字母，总共100瓦。我想做一个所有40个水平和垂直的词都是有效的。一组可用的瓷砖包含：
- 12 x E
- 9 x A，I
-
- 8 x O
- 6 x N，R，T
- 4 x D，L，S，U
- 3 x G
- 2 x B，C，F，H，M，P，V，W，Y，空白瓦片（通配符）
- 1 x K，J，Q，X，Z
可以此处（700KB）。有大约12,000个有效的5个字母的单词。
这里有一个示例，其中所有20个水平词都有效：
ZOWIE | PINOT
YOGIN | OC t AD< = blank用作't'
XEBEC | NALED
WAITE | MERLE
VINER | LUTEA
--------- + ---------
USNEA | KNOSP
TAVER | JOLED
SOFTA | IAMBI
RIDGY | HAIT h <= blank用作'h'
QURSH | GROUF
我想创建一个所有垂直的都是有效的。你可以帮我解决吗这不是功课这是一个朋友问我要帮忙的问题。
最终编辑：已解决是一个解决方案。
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板，像格伦说，看到如果其中四个可以组合。
编辑：这是我的代码的版本2。
#include< stdio.h>
#include< stdlib.h>
#include< string.h>
#include< stdbool.h>
typedef union节点节点;
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; （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; （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-> tile [i];
for（d = c-> next; d！= NULL; d = d-> next）{
match = true; （i = 0; i< 27; i ++）{
if（three_total [i] + d-> tiles [i]！= full_bag [i]）{
match =假;
break;
}
}
if（match）{
printf（\\\
Board Found！\\\
\\\
）; （i = 0; i< 5; i ++）{
printf（％s\\\
，a-> rows [i] - > string）
}
printf（\\\
）; （i = 0; i< 5; i ++）{
printf（％s\\\
，b-> rows [i] - > string）
}
printf（\\\
）; （i = 0; i <5; i ++）{
printf（％s\\\
，c-> rows [i] - > string）
}
printf（\\\
）; （i = 0; i< 5; i ++）{
printf（％s\\\
，d-> rows [i] - > string）
}
exit（0）;
}
}
}
}
}
void snapshot（）{
snap * shot = malloc（sizeof snap））;
int i; （i = 0; i <5; i ++）{
printf（％s\\\
，htrie [i] - > string）
shot-> rows [i] = htrie [i];
shot-> cols [i] = vtrie [i];
}
printf（\\\
）; （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; （i = 0; i <5; i ++）{
if（shot-> rows [i]！= place-> cols [i]）{
transpose = false ;
break;
}
}
place = place-> next;
}
if（转置）{
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&& b $ b 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; （i = 0; i< 26; i ++）
{
root-> child [i] = NULL; （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个瓷砖，并且仍在运行。 p>
编辑2：这是我生成的所有有效的5x5块的列表。 http://web.cs.sunyit.edu/~levyt/solutions.rar
编辑3：嗯，似乎我的瓦片使用情况跟踪有一个错误，因为我刚刚在我的输出文件中找到一个使用5个Z的块。 p>
COSTE
ORCIN
SCUZZ
TIZZY
ENZYM
编辑4：这是最终产品。
code> #include< stdio.h>
#include< stdlib.h>
#include< string.h>
#include< stdbool.h>
typedef union节点节点;
union node {
node * child [26];
char string [6];
};
node * root;
node * vtrie [5];
node * htrie [5];
int分数;
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,10,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; （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; （i = 0; i <5; i ++）{
printf（％s\\\
，htrie [i] - > string）
（i = 0; i <27; i ++）{
printf（％c％d，'A'+ i，bag [i]）;
}
printf（\\\
）;
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&& b $ b 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; （i = 0; i< 26; i ++）
{
root-> child [i] = NULL; （i = 0; i <5; i ++）{
vtrie [i] = root;
}
htrie [i] = root; （i = 0; i< 27; i ++）{
}
（i = 0; 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个字母数字成反比。然后，当我找到一个有效的块时，我将总结瓦片值，如果得分是我还没有看到的最好的，我会打印出来的块。
对于第一个块，我删除了空白的瓦片，认为最后一个块将需要最大的灵活性。让它运行，直到我没有看到一个更好的块出现一段时间，我选择了最好的块，并从包中删除它的瓷砖，并再次运行程序，得到第二个块。我重复了这个第三个街区。然后对于最后一个块，我添加了空白并使用了它找到的第一个有效块。
For tile checking in scrabble, you make four 5x5 grids of letters totalling 100 tiles. I would like to make one where all 40 horizontal and vertical words are valid. The set of available tiles contains:
- 12 x E
- 9 x A, I
- 8 x O
- 6 x N, R, T
- 4 x D, L, S, U
- 3 x G
- 2 x B, C, F, H, M, P, V, W, Y, blank tile (wildcard)
- 1 x K, J, Q, X, Z
The dictionary of valid words is available here (700KB). There are about 12,000 valid 5 letter words.
Here's an example where all 20 horizontal words are valid:
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
I'd like to create one where all the vertical ones are also valid. Can you help me solve this? It is not homework. It is a question a friend asked me for help with.
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
Here's a photo of it constructed with my scrabble set. http://twitpic.com/3wn7iu
This one was easy to find once I had the right approach, so I bet you could find many more this way. See below for methodology.
Construct a prefix tree from the dictionary of 5 letter words for each row and column. Recursively, a given tile placement is valid if it forms valid prefixes for its column and row, and if the tile is available, and if the next tile placement is valid. The base case is that it is valid if there is no tile left to place.
It probably makes sense to just find all valid 5x5 boards, like Glenn said, and see if any four of them can be combined. Recursing to a depth of 100 doesn't sound like fun.
Edit: Here is version 2 of my code for this.
#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;
}
This tries the infrequent letters first, which I'm no longer sure is a good idea. It starts to get bogged down before it makes it out of the boards starting with x. After seeing how many 5x5 blocks there were I altered the code to just list out all the valid 5x5 blocks. I now have a 150 MB text file with all 4,430,974 5x5 solutions.
I also tried it with just recursing through the full 100 tiles, and that is still running.
Edit 2: Here is the list of all the valid 5x5 blocks I generated. http://web.cs.sunyit.edu/~levyt/solutions.rar
Edit 3: Hmm, seems there was a bug in my tile usage tracking, because I just found a block in my output file that uses 5 Zs.
COSTE
ORCIN
SCUZZ
TIZZY
ENZYM
Edit 4: Here is the final product.
#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;
}
After finding out how many blocks there were (nearly 2 billion and still counting), I switched to trying to find certain types of blocks, in particular the difficult to construct ones using uncommon letters. My hope was that if I ended up with a benign enough set of letters going in to the last block, the vast space of valid blocks would probably have one for that set of letters.
I assigned each tile a value inversely proportional to the number of 5 letter words it appears in. Then, when I found a valid block I would sum up the tile values, and if the score was the best I had yet seen, I would print out the block.
For the first block I removed the blank tiles, figuring that the last block would need that flexibility the most. After letting it run until I had not seen a better block appear for some time, I selected the best block, and removed the tiles in it from the bag, and ran the program again, getting the second block. I repeated this for the 3rd block. Then for the last block I added the blanks back in and used the first valid block it found.
这篇关于拼字砖检查的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
