[Word Game]Quiddler Solver Algorithm

Question

Quiddler Solver

I have a card game called Quiddler that I'm trying to write an algorithm to solve, but when I try and solve it linearly its very slow and inefficient.

The Game (Step by step):

1. Each player is dealt a number of cards between 3 and 10, each card has either one or two letters on it.
2. The player then tries to make a single or multiple words from the cards they are given, without having excess cards.

While I tried my best at an algorithm to preform these seeming easy tasks it takes over 20 seconds to find all the answers for even a medium length hand.

I used a dictionary such as this one for my wordlist. I linearly check the number of letters in my hand and I compare it to the words in the list assuming they are of equal or shorter length. While this works it takes far too long.

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

Example Hand: cards=['i','d','o','n']

Answers(According to my algorithm): di no, di on, do in, id no, id on, in do, in od, 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'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)

I import a precompiled list of the words called dict from wordlist.

I hope somebody can help me out with my algorithm design because it needs improvement, thanks.

Somebody suggested using a DAWG, but I'm not doing any word lookups. In which case I still have to cycle the words to check the letters, unless I'm thinking along the wrong lines?

Answer 1

You can try storing the word list as a directed acyclic word graph (DAWG) or a trie for fast lookups.

Place the first letter and use the DAWG/trie to find out all the possibilities for the second letter, and so on. Use backtracking when no more letters can be placed, or when a solution has been found and you want the next one.

This algorithm should be roughly linear in the number of solutions, and if written efficiently should be able to solve your problem in a few milliseconds for 10 cards. Note though that the number of solutions grows rapidly as you add more cards.