c++ - [文字游戏]Quiddler Solver Algorithm

Question

Quiddler 求解器

我有一个名为 Quiddler 的纸牌游戏，我正在尝试编写一种算法来解决，但是当我尝试线性解决它时，它非常缓慢且效率低下。

游戏(一步一步):

1. 每个玩家都会拿到 3 到 10 张之间的牌，每张牌上都有一个或两个字母。
2. 然后玩家尝试从给定的卡片中拼出一个或多个单词，没有多余的卡片。

虽然我尽最大努力使用算法来执行这些看似简单的任务，但即使是中等长度的手，也需要 20 多秒才能找到所有答案。

我用了字典such as this one对于我的单词列表。我线性检查手中字母的数量，并将其与列表中的单词进行比较，假设它们的长度相等或更短。虽然这很有效，但花费的时间太长了。

我希望有人能帮我解决这个问题，最好是使用 Perl、Python 或 C/C++。

示例手: cards=['i','d','o','n']

答案(根据我的算法): 不， 狄上， 做， 证件号码， 身份证上， 在做， 在外径， 恐龙， 没有

我的 Python 算法:

import timeit
from wordlist import *
#Quiddler Solver
print 'Dictionary loaded\n'

#Define our hand
cards=['i','d','o','n']

#Count the letters in a word
def cntLetters(word):   #Surely there's a better way?
    lettercnt={97:0,98:0,99:0,100:0,101:0,102:0,103:0,104:0,105:0,106:0,107:0,108:0,109:0,110:0,111:0,112:0,113:0,114:0,115:0,116:0,117:0,118:0,119:0,120:0,121:0,122:0}
    for v in word:
        lettercnt[ord(v)]+=1
    return lettercnt

#Check the letters to make sure our hand has at least what the word has
def cmpList(list1,list2):
    for k,v in list1.iteritems():
        if list2[k]<=v:
            pass
        else:
            return False
    return True

#Check to make sure cards with more than one letter are together in the word.
def has(word):
    for v in cards:
        if len(v)>1:
            if v in word:
                pass
            else:
                return False
    return True

def solve():
    rawhand=''.join(cards).lower()
    hand=cntLetters(rawhand)
    handl=len(rawhand)
    buff=[]
    for v in dict:  #Add all words that have at least the letters in our hand to buff
        if len(v)<=handl and cmpList(hand,cntLetters(v)):
            if has(v):
                buff.append(v)
    for v in range(0,int((len(buff)/2)+1)): #Find 2 words that can be used together to make a play
        for n in buff:
            if len(n)==(handl-len(buff[v])):
                if hand==cntLetters(buff[v]+n):
                    print buff[v],n
    for v in range(0,int((len(buff)/3)+1)): #This is a bit overkill since it finds so much stuff, need to tune it
        for n in buff:
            if (len(n))<=len(buff[v]):
                for x in buff:
                    if len(x)==(handl-len(buff[v])-len(n)):
                        if hand==cntLetters(buff[v]+n+x):
                            print buff[v],n,x
    for v in buff:  #Print the single words that can be made
        if len(v)==handl:
            print v

t = timeit.Timer(stmt=solve)
print 'Search took %.2f seconds'%t.timeit(number=1)

我从 wordlist 中导入名为 dict 的预编译单词列表。

我希望有人能帮助我完成我的算法设计，因为它需要改进，谢谢。

有人建议使用 DAWG，但我没有进行任何单词查找。在这种情况下，我仍然必须循环单词来检查字母，除非我的思路有误？

Answer 1

您可以尝试将单词列表存储为 directed acyclic word graph (DAWG) 或 trie用于快速查找。

放置第一个字母并使用 DAWG/trie 找出第二个字母的所有可能性，依此类推。当无法放置更多字母时，或者当找到解决方案并且您想要下一个时，使用回溯法。

这个算法应该在解决方案的数量上大致呈线性关系，如果编写得高效，应该能够在几毫秒内解决 10 张卡片的问题。请注意，随着您添加更多卡片，解决方案的数量会迅速增加。