[Text Game] Quiddler Solver Algorithm

Question

Quiddler Solver

I have a card game called Quiddler, which I am trying to write an algorithm for solving, but when I try and solve it linearly it is very slow and inefficient.

The game (step by step):

• Each player is assigned a number of cards from 3 to 10, each card has one or two letters on it.
• The player then tries to make one or more words from the cards they received, without any extra cards.

While I tried my best according to the algorithm to present these seemingly easy tasks, it took more than 20 seconds to find all the answers even for an average length.

I used a dictionary such as this for my list of words. I linearly check the number of letters in my hand, and I compare them with the words in the list, assuming they have the same or shorter length. Although this works, it takes too much time.

I hope someone can help me here, preferably in Perl, Python or C / C ++.

Example: cards = ['i', 'D', 'o', 'n']

Answers (according to my algorithm): di no, di on, do, id no, id on, do, I nod, Dino, Nodi

My algorithm in 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 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)

I am importing a precompiled list of words called dict from a list of words.

I hope someone can help me develop my algorithm because it needs to be improved, thanks.

- DAWG, . , ?

Answer 1

(DAWG) trie .

DAWG/trie, .. backtracking, , , .

, 10 . , , .

Answer 2

, , NP-, , DAWG, .