[文字游戏]Quiddler 解法算法
Quiddler 解题器
我有一个叫 Quiddler 的纸牌游戏，我正在尝试写一个算法来解决它，但当我试着用线性的方法解决时，速度非常慢，效率也不高。
游戏规则（一步一步来）：
- 每位玩家会发到3到10张牌，每张牌上有一个或两个字母。
- 玩家需要用手中的牌组成一个或多个单词，不能有多余的牌。
虽然我尽力写了一个算法来完成这些看似简单的任务，但即使是中等长度的牌组，找到所有答案也要花超过20秒。
我使用了一个字典 这样的字典作为我的单词列表。我线性地检查手中牌的字母数量，并将其与列表中的单词进行比较，假设它们的长度相等或更短。虽然这样做是可行的，但花费的时间太长了。
我希望有人能帮我，最好是用 Perl、Python 或 C/C++。
示例牌组： cards=['i','d','o','n']
根据我的算法得到的答案： di no, di on, do in, id no, id on, in do, in od, dino, nodi
我用 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)
我从单词列表中导入了一个预编译的单词列表，叫做 dict。
我希望有人能帮我改进我的算法设计，因为它需要改进，谢谢。
有人建议使用 DAWG，但我并不进行任何单词查找。在这种情况下，我仍然需要循环检查字母，除非我想错了方向？
2 个回答
1
你的问题可以很简单地转化为集合覆盖问题，而集合覆盖问题是一个NP完全的问题。这意味着虽然你可能通过使用DAWG（有向无环字典树）来做一些小的改进，但目前还没有找到一个高效的解决办法。