[文字游戏]魁德勒求解算法

2024-03-29 14:55:25 发布

您现在位置:Python中文网/ 问答频道 /正文

魁德勒解算器

我有一个纸牌游戏叫做Quiddler,我正试图写一个算法来求解,但是当我试图线性求解它时,它非常缓慢且效率低下。在

游戏(一步一步):

  1. 每一个牌手都会得到3到10张牌,每张牌上有一个或两个字母。在
  2. 然后,玩家尝试从他们得到的牌中做出一个或多个单词,而不必有多余的牌。在

当我尽我最大的努力去完成这些看似简单的任务时,即使是中等长度的手,也要花20多秒才能找到所有的答案。在

我用字典such as this one作为我的词表。我线性地检查我手上的字母数量,并将其与列表中的单词进行比较,假设它们长度相等或更短。虽然这是可行的,但却需要太长时间。在

我希望有人能帮助我,最好是在Perl,Python或C/C++。在

示例手: 卡片=['i'、'd'、'o'、'n']

答案(根据我的算法): di编号, 打开, 进去吧, 身份证号码, 身份证开了, 在做, 在od中, 恐龙, 诺迪

我的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的预编译单词列表。

我希望有人能帮我设计算法,因为它需要改进,谢谢。在

有人建议用破折号,但我不查单词。在这种情况下,我还是要循环单词来检查字母,除非我的思路有误?在


Tags: thetoin算法forlenreturnif
2条回答

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

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

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

从你的问题到设置覆盖有一个非常直接的简化,这是NP完全的,所以虽然你可以使用DAWGs进行一些小的改进,但是还没有已知的有效的解决方案。在

相关问题 更多 >