Подтвердить что ты не робот

Проверка плитки

Для проверки плитки в scrabble вы делаете четыре сетки 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

Словарь допустимых слов доступен здесь (700 КБ). Есть около 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

Я хотел бы создать тот, где все вертикальные также действительны. Можете ли вы помочь мне решить эту проблему? Это не домашнее задание. Это вопрос, который друг попросил меня о помощи.

4b9b3361

ОТВЕТЫ

Ответ 1

Final Edit: Решено! Вот решение.

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;
}

Сначала это пробует нечастые буквы, и я не уверен, что это хорошая идея. Он начинает увязнуть, прежде чем он выйдет из досок, начиная с х. Посмотрев, сколько блоков размером 5x5 я изменил код, просто перечислил все допустимые блоки 5x5. Теперь у меня есть текстовый файл объемом 150 МБ со всеми решениями 4 430 974 5x5.

Я также пробовал его с помощью всего лишь повторения через 100 плит, и это все еще работает.

Изменить 2: Вот список всех допустимых 5x5 блоков, которые я сгенерировал. http://web.cs.sunyit.edu/~levyt/solutions.rar

Edit 3: Хм, кажется, что в моем отслеживании использования фрагментов произошла ошибка, потому что я только что нашел блок в своем выходном файле, который использует 5 Zs.

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 миллиарда и все еще считалось), я переключился на поиск определенных типов блоков, в частности трудных для построения, используя необычные буквы. Я надеялся, что если бы у меня получилось достаточно мягкое множество букв, идущих к последнему блоку, обширное пространство допустимых блоков, вероятно, имело бы один для этого набора букв.

Я назначил каждому плиту значение, обратно пропорциональное количеству 5 буквенных слов, которые он появляется. Тогда, когда я нашел действительный блок, я бы подвел итоги плитки, и если бы оценка была лучшей, которую я еще видел, Я бы распечатал блок.

Для первого блока я удалил пустые фрагменты, считая, что последний блок понадобится для большей гибкости. После того, как я пропустил его до тех пор, пока не увидел, что в течение некоторого времени появится лучший блок, я выбрал лучший блок и удалил в нем плитку из мешка и снова запустил программу, получив второй блок. Я повторил это для третьего блока. Затем для последнего блока я добавил пробелы и использовал первый допустимый блок, который он нашел.

Ответ 2

Я бы подошел к проблеме (наивно, конечно), пессимистично. Я бы попытался доказать, что не было решения 5x5, и поэтому, конечно, не четыре решения 5x5. Чтобы доказать отсутствие решения 5x5, я попытался бы построить один из всех возможностей. Если бы моя гипотеза потерпела неудачу, и мне удалось построить решение 5x5, тогда у меня был бы способ построить решения 5x5, и я попытался бы построить все (независимые) решения 5x5. Если бы было по крайней мере 4, я бы определил, удовлетворяет ли какая-либо комбинация ограничениям количества букв.

[Edit] Null Set определил, что есть "4 430 974 5x5 решений". Действительно ли это? Я имею в виду, что у нас есть ограничение на количество писем, которые мы можем использовать. Это ограничение можно выразить как граничный вектор BV = [9, 2, 2, 4,...], соответствующий пределам на A, B, C и т.д. (Вы видите этот вектор в коде Null Set). Решение 5x5 справедливо, если каждый член его вектора счета букв меньше соответствующего члена в BV. Было бы легко проверить, действительно ли решение 5x5 является действительным по мере его создания. Возможно, число 4 430 974 может быть уменьшено, скажем, N.

Независимо, мы можем сформулировать проблему как: найти четыре вектора счета числа среди N, сумма которых равна BV. Возможны (N, 4) возможные суммы ( "N выбрать 4" ). При N, равном 4 миллионам, это все еще порядка 10 ^ 25 --- не обнадеживающее число. Возможно, вы могли бы искать четыре, чьи первые члены суммируют до 9, и если они проверяют, что их второе слагаемое суммируется до 2 и т.д.

Я бы заметил, что после выбора 4 из N вычисления независимы, поэтому, если у вас многоядерный компьютер, вы можете ускорить это с помощью параллельного решения.

[Edit2] Параллелизация, вероятно, не имела бы большого значения. На данный момент я мог бы оптимистично взглянуть: есть, конечно, более 5x5 решений, чем я ожидал, поэтому могут быть и более окончательные решения, чем ожидалось. Возможно, вам не придется далеко ходить в 10 ^ 25, чтобы поразить его.

Ответ 3

Вот как бы я попробовал это. Сначала создадим дерево префикса.

Выберите слово и поместите его горизонтально сверху. Выберите слово и поместите его вертикально. Изменяйте их до исчерпанных опций. При чередовании вы начинаете фиксировать первые буквы и устраняете множество несоответствующих слов. Если вы действительно найдете такой квадрат, тогда сделайте проверку, могут ли они быть сделаны с этими частями.

Для квадратов 5x5: после некоторого размышления он не может быть хуже, чем 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

что не так уж плохо.

Возможно, кто-то может лучше проанализировать проблему. Но поиск слов должен все же сходиться довольно быстро.

Больше можно устранить, злоупотребляя нечастыми буквами. По существу найдите все слова, которые имеют нечастые буквы. Попробуйте сделать соответствующие позиции для каждой буквы. Постройте набор допустимых букв для каждой позиции.

Например, скажем, у нас есть четыре слова с буквой 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

В принципе, если у нас есть несколько слов, которые содержат нечастую букву X в слове S в позиции N, означает, что другие слова, которые находятся в этой матрице, должны иметь букву, которая также находится в S в позиции n.

Формула

  • Найдите все слова, которые содержат нечастую букву X в позиции 1 (следующая итерация 2, 3...)
  • Сделайте букву A из букв в этих словах
  • Сохраняйте только те слова из словаря, у которого есть буква из набора A в позиции 1
  • Попытайтесь поместить их в матрицу (с помощью первого метода)
  • Повторить с позицией 2

Ответ 4

Я начинаю с чего-то более простого.

Ниже приведены некоторые результаты:

   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", следует рассматривать как одно и то же решение. Но перенос строк со столбцами следует рассматривать как другое решение. Надеюсь, это имеет смысл.

Ответ 5

Вот много предварительно вычисленных 5х5. Оставленный как упражнение для чтения, чтобы найти 4 совместимых: -)

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