如何高效求解NYT Spelling Bee游戏的最优字母组合？

NYT Spelling Bee是一款拼字游戏，规则如下：

• 给定包含1个中心字母的7个字母，需找出至少4个字母且必须包含中心字母的单词。
• 计分规则：4字母单词得1分，长度大于4的单词得对应长度的分数；使用全部7个字母的pangrams（全字母词）额外加7分。

我希望找到能产生最高得分的7字母组合（含中心字母）。

• 之前见过一种反向贪心方法：从全字母集合开始，每次尝试移除单个字母并重新计算子集得分，结果接近最优但无法保证是最优解。
• 我尝试改用一致代价搜索（Uniform-Cost Search，本质是Dijkstra算法）：从代表全字母集合的节点出发，探索移除单个字母后的邻节点，用最大优先队列始终优先处理 frontier 中得分最高的邻节点，首次遇到含7个字母的节点时终止搜索。
• 但该方法存在严重效率问题：大量中间节点得分相同，导致需要遍历2^26个可能节点中的极大部分，计算量极大；同时我找不到适用于A*算法的可采纳启发式函数，无法进一步剪枝优化。
• 我想到一个验证单词是否符合字母集合的技巧：将单词预处理为字母位掩码——若单词包含字母表第i个字母，则掩码的第i位设为1。判断时只需检查word_mask | letter_mask == letter_mask，即可确认单词仅使用掩码中的字母。
• 实现现状：用Python/PyPy和C++分别编写了示例实现，但均无法在1小时内运行完成；且当前实现未考虑pangrams和中心字母规则（这或许能大幅减少搜索量）。

可通过以下命令生成符合要求的单词列表：

grep -P "^[a-z]{4,}$" /usr/share/dict/words > words.txt

from string import ascii_lowercase

S = ascii_lowercase  # 字母表 Σ

with open("words.txt") as f:
    L0 = f.read().splitlines()  # 原始单词列表

# 过滤出不同字母数量≤7的单词
L = list(filter(lambda w: len(set(w)) <= 7, L0))

print(len(L0), len(L))
print(L[:20])

# 将单词转换为26位整数的位掩码：每个字母对应一位，存在则置1
bitsets = [0] * len(L)
for i in range(len(L)):
    for c in L[i]:
        bitsets[i] |= 1 << (ord(c) - ord('a'))
    
    if i < 20:
        print(L[i].ljust(16), bin(bitsets[i])[2:].zfill(26))

# 计算单个单词的得分
def word_score(word):
    if len(word) == 4:
        return 1
    else:
        return len(word)

# 计算字母掩码对应的总得分（返回负值用于用最小堆模拟最大堆）
def mask_score(mask):
    s = 0
    for i in range(len(L)):
        if mask | bitsets[i] == mask:
            s += word_score(L[i])
    return -s 


from heapq import heappop, heappush

# 基于Dijkstra算法的图搜索（修改为计算节点权重）
start_mask = (1 << len(S)) - 1 
start_node = (mask_score(start_mask), start_mask)

pq = [start_node]
visited = set()

while True:
    score, mask = heappop(pq)

    print(score, "".join(S[i] if mask & (1 << i) else ' ' for i in range(26)))

    if mask.bit_count() == 7: 
        break

    # 将未访问的邻节点加入队列
    for i in range(len(S)):
        if mask & (1 << i):
            new_mask = mask & ~ (1 << i)
            if new_mask in visited:
                continue
            new_score = mask_score(new_mask)
            new_node = (new_score, new_mask)
            heappush(pq, new_node)
            visited.add(new_mask)

内容的提问来源于Stack Exchange，提问作者qwr