Ruzzle板包含哪些最独特的单词？

Question

对于智能手机,有一款名为Ruzzle的游戏.

这是一个找到游戏的词.

快速说明:
游戏板是一个4x4网格字母.
您从任何单元格开始,尝试通过向上,向下,向左,向右或对角线拖动来拼写单词.
电路板不会换行,您不能重复使用已选择的字母.

平均而言,我的朋友和我发现了大约40个单词,在本轮结束时,游戏会告诉您可以获得多少可能的单词.这个数字通常约为250 - 350.
我们想知道哪个委员会会产生最多可能的单词.

我如何寻找最佳板？
我用C编写了一个程序,它占用了16个字符并输出了所有相应的单词.
测试超过80,000个单词,处理大约需要一秒钟.

问题:
游戏板排列的数量是26 ^ 16.
那是43608742899428874059776(43 sextillion).

我需要某种启发式方法.
我应该跳过要么所有板ž,q,X,等等,因为他们预计不会有很多的话？我不想在不确定的情况下排除一封信.
每个电路板也有4个重复,因为旋转电路板仍会产生相同的结果.
但即使有这些限制,我也不认为我有足够的时间来找到答案.

也许董事会的产生不是答案.
有没有更快捷的方法来查找单词列表中的答案？

Answer 1

tldr;

S   E   R   O
P   I   T   S
L   A   N   E
S   E   R   G

或其任何反思.

这个板包含1212个单词(事实证明,你可以排除'z','q'和'x').

首先,事实证明你正在使用错误的字典.在没有与Ruzzle的字数完全匹配之后,我调查了一下,似乎Ruzzle使用了一个名为TWL06的字典,它有大约180,000个单词.不要问我它代表什么,但它在txt中免费提供.

我还编写了代码来查找给出16字符板的所有可能的单词,如下所示.它将字典构建为树形结构,然后在有文字被发现时,几乎只是递归地进行.它按照长度顺序打印它们.STL集结构保持唯一性.

#include <cstdlib>
#include <ctime>
#include <map>
#include <string>
#include <set>
#include <algorithm>
#include <fstream>
#include <iostream>

using namespace std;

struct TreeDict {

    bool existing;
    map<char, TreeDict> sub;

    TreeDict() {
        existing = false;
    }

    TreeDict& operator=(TreeDict &a) {

        existing = a.existing;
        sub = a.sub;
        return *this;
    }

    void insert(string s) {

        if(s.size() == 0) {

            existing = true;
            return;
        }

        sub[s[0]].insert(s.substr(1));
    }

    bool exists(string s = "") {

        if(s.size() == 0)
            return existing;

        if(sub.find(s[0]) == sub.end())
            return false;

        return sub[s[0]].exists(s.substr(1));
    }

    TreeDict* operator[](char alpha) {

        if(sub.find(alpha) == sub.end())
            return NULL;

        return &sub[alpha];
    }
};

TreeDict DICTIONARY;

set<string> boggle_h(const string board, string word, int index, int mask, TreeDict *dict) {

    if(index < 0 || index >= 16 || (mask & (1 << index)))
        return set<string>();

    word += board[index];
    mask |= 1 << index;
    dict = (*dict)[board[index]];

    if(dict == NULL)
        return set<string>();

    set<string> rt;

    if((*dict).exists())
        rt.insert(word);

    if((*dict).sub.empty())
        return rt;

    if(index % 4 != 0) {

        set<string> a = boggle_h(board, word, index - 4 - 1, mask, dict);
        set<string> b = boggle_h(board, word, index - 1, mask, dict);
        set<string> c = boggle_h(board, word, index + 4 - 1, mask, dict);

        rt.insert(a.begin(), a.end());
        rt.insert(b.begin(), b.end());
        rt.insert(c.begin(), c.end());
    }

    if(index % 4 != 3) {

        set<string> a = boggle_h(board, word, index - 4 + 1, mask, dict);
        set<string> b = boggle_h(board, word, index + 1, mask, dict);
        set<string> c = boggle_h(board, word, index + 4 + 1, mask, dict);

        rt.insert(a.begin(), a.end());
        rt.insert(b.begin(), b.end());
        rt.insert(c.begin(), c.end());
    }

    set<string> a = boggle_h(board, word, index + 4, mask, dict);
    set<string> b = boggle_h(board, word, index - 4, mask, dict);

    rt.insert(a.begin(), a.end());
    rt.insert(b.begin(), b.end());

    return rt;
}

set<string> boggle(string board) {

    set<string> words;
    for(int i = 0; i < 16; i++) {

        set<string> a = boggle_h(board, "", i, 0, &DICTIONARY);
        words.insert(a.begin(), a.end());
    }
    return words;
}

void buildDict(string file, TreeDict &dict = DICTIONARY) {

    ifstream fstr(file.c_str());
    string s;

    if(fstr.is_open()) {
        while(fstr.good()) {

            fstr >> s;
            dict.insert(s);
        }
        fstr.close();
    }
}

struct lencmp {
    bool operator()(const string &a, const string &b) {

        if(a.size() != b.size())
            return a.size() > b.size();
        return a < b;
    }
};

int main() {

    srand(time(NULL));

    buildDict("/Users/XXX/Desktop/TWL06.txt");

    set<string> a = boggle("SEROPITSLANESERG");
    set<string, lencmp> words;
    words.insert(a.begin(), a.end());
    set<string>::iterator it;
    for(it = words.begin(); it != words.end(); it++)
        cout << *it << endl;
    cout << words.size() << " words." << endl;
}

随机生成电路板并对它们进行测试并没有太有效,预计,我并没有真正打扰它,但如果它们超过200个字我会感到惊讶.相反,我改变了电路板生成以生成字母,其字母与TWL06中的频率成比例分布,通过快速累积频率(频率减少100倍)实现,低于此值.

string randomBoard() {

    string board = "";
    for(int i = 0; i < 16; i++)
        board += (char)('A' + rand() % 26);
    return board;
}

char distLetter() {

    int x = rand() % 15833;
    if(x < 1209) return 'A';
    if(x < 1510) return 'B';
    if(x < 2151) return 'C';
    if(x < 2699) return 'D';
    if(x < 4526) return 'E';
    if(x < 4726) return 'F';
    if(x < 5161) return 'G';
    if(x < 5528) return 'H';
    if(x < 6931) return 'I';
    if(x < 6957) return 'J';
    if(x < 7101) return 'K';
    if(x < 7947) return 'L';
    if(x < 8395) return 'M';
    if(x < 9462) return 'N';
    if(x < 10496) return 'O';
    if(x < 10962) return 'P';
    if(x < 10987) return 'Q';
    if(x < 12111) return 'R';
    if(x < 13613) return 'S';
    if(x < 14653) return 'T';
    if(x < 15174) return 'U';
    if(x < 15328) return 'V';
    if(x < 15452) return 'W';
    if(x < 15499) return 'X';
    if(x < 15757) return 'Y';
    if(x < 15833) return 'Z';
}

string distBoard() {

    string board = "";
    for(int i = 0; i < 16; i++)
        board += distLetter();
    return board;
}

这显然更有效,非常容易实现400多个字板.我让它保持运行(比我想要的时间更长),检查了超过一百万个电路板后,发现的最高值约为650字.这仍然是随机生成,这有其局限性.

相反,我选择了一种贪婪的最大化策略,其中我会采用一个板并对其进行一些小改动,然后只有在增加字数时才提交更改.

string changeLetter(string x) {

    int y = rand() % 16;
    x[y] = distLetter();
    return x;
}

string swapLetter(string x) {

    int y = rand() % 16;
    int z = rand() % 16;
    char w = x[y];
    x[y] = x[z];
    x[z] = w;
    return x;
}

string change(string x) {

    if(rand() % 2)
        return changeLetter(x);
    return swapLetter(x);
}

int main() {

    srand(time(NULL));

    buildDict("/Users/XXX/Desktop/TWL06.txt");

    string board = "SEROPITSLANESERG";
    int locmax = boggle(board).size();
    for(int j = 0; j < 5000; j++) {

        int changes = 1;

        string board2 = board;
        for(int k = 0; k < changes; k++)
            board2 = change(board);

        int loc = boggle(board2).size();
        if(loc >= locmax && board != board2) {
            j = 0;
            board = board2;
            locmax = loc;
        }
    }
}

尽管随机化了起点,但这很快就让我获得了1000多个字板,字母模式大致相似.是什么让我相信所提供的电路板是最好的电路板,它是在最大化随机电路板的前100次尝试中反复出现的,或其中的一种反射.

怀疑主义的最大原因是这种算法的贪婪,并且这会以某种方式导致算法错过更好的板.所做的微小变化在结果上非常灵活 - 也就是说,它们有能力将网格从其(随机)起始位置完全转换.可能的更改数量,新信函的26*16和字母交换的16*15,都明显小于5000,允许连续丢弃的更改数量.

程序能够在前100个时间内重复该板输出的事实意味着局部最大值的数量相对较小,并且存在未发现的最大低值的概率.

虽然贪婪似乎是直觉上正确的 - 通过随机板的delta变化到达给定的网格实际上不太可能 - 并且两个可能的变化,交换和一个新的信件似乎包含了所有可能的改进,我更改程序以允许它在检查增加之前进行更多更改.这又一次又一次地回到同一块板上.

int main() {

    srand(time(NULL));

    buildDict("/Users/XXX/Desktop/TWL06.txt");

    int glomax = 0;
    int i = 0;
    while(true) {

        string board = distBoard();
        int locmax = boggle(board).size();
        for(int j = 0; j < 500; j++) {

            string board2 = board;
            for(int k = 0; k < 2; k++)
                board2 = change(board);

            int loc = boggle(board2).size();
            if(loc >= locmax && board != board2) {
                j = 0;
                board = board2;
                locmax = loc;
            }
        }

        if(glomax <= locmax) {
            glomax = locmax;
            cout << board << " " << glomax << " words." << endl;
        }

        if(++i % 10 == 0)
            cout << i << endl;
    }
}

迭代了这个循环大约1000次,这个特殊的电路板配置出现了大约10次,我非常有信心这是现在Ruzzle板上最独特的单词,直到英语变化.