c++ - 什么 Ruzzle 板包含最独特的单词？

Question

对于智能手机，有这个游戏叫Ruzzle .

这是一个找词游戏。

快速说明:
游戏板是一个 4x4 的字母网格。
您可以从任意单元格开始，通过向上、向下、向左、向右或对角线拖动来尝试拼写单词。
棋盘不换行，您不能重复使用已经选择的字母。

平均而言，我和我的 friend 会找到大约 40 个单词，并且在回合结束时，游戏会告诉您您可能会找到多少个单词。这个数字通常约为 250 - 350。
我们想知道哪个板会产生最多的可能单词。

我将如何找到最佳板？
我用 C 编写了一个程序，它接受 16 个字符并输出所有适当的单词。
测试超过 80,000 个单词，处理大约需要一秒钟。

问题:
棋盘排列数为26^16。
那是 43608742899428874059776(43 十亿)。

我需要某种启发式方法。
我是否应该跳过所有具有 z、q、x、etc 的板，因为它们应该没有一样多的话？我不想在不确定的情况下排除字母。
每 block 板也有 4 个拷贝，因为旋转板仍然会给出相同的结果。
但即使有这些限制，我认为我一生中也没有足够的时间找到答案。

也许板生成不是答案。
有没有一种更快的方法可以通过查看单词列表找到答案？

Answer 1

长话短说；

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 个单词。这基本上仍然是随机生成，并且有其局限性。

相反，我选择了一种贪婪的最大化策略，在这种策略中，我会拿一 block 板对其进行小的更改，然后仅在它增加字数时才提交更改。

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 次奇数尝试最大化随机棋盘的过程中反复出现的，或者它的各种反射(reflect)之一。

怀疑的最大原因是该算法的贪婪性，这会以某种方式导致该算法错过更好的棋盘。所做的小改动在结果上非常灵活——也就是说，它们有能力从(随机的)起始位置完全改变网格。可能的变化数量，新字母为 26*16，字母交换为 16*15，均明显小于 5000，即允许的连续丢弃变化数。

程序能够在前 100 次奇数次内重复此板输出的事实意味着局部最大值的数量相对较少，并且存在未发现的最大值的概率较低。

尽管贪婪在直觉上似乎是正确的——从随机棋盘的增量变化到达给定网格的可能性确实不小——而且两种可能的变化，交换和新字母似乎包含了所有可能改进，我更改了程序以允许它在检查增加之前进行更多更改。这再次返回相同的板，重复。

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 板，直到英语语言发生变化。