Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Scramble Solver Output
FoundWord(word='a', locations=[Location(row=2, col=0)])
FoundWord(word='al', locations=[Location(row=2, col=0), Location(row=1, col=1)])
FoundWord(word='alice', locations=[Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=2), Location(row=2, col=3), Location(row=3, col=2)])
FoundWord(word='alien', locations=[Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=2), Location(row=3, col=2), Location(row=3, col=3)])
FoundWord(word='alin', locations=[Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='aline', locations=[Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='alit', locations=[Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=2), Location(row=2, col=1)])
FoundWord(word='alite', locations=[Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=2), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='alt', locations=[Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=1)])
FoundWord(word='alter', locations=[Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='altern', locations=[Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1), Location(row=3, col=0)])
FoundWord(word='altin', locations=[Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='alur', locations=[Location(row=2, col=0), Location(row=1, col=1), Location(row=1, col=2), Location(row=0, col=2)])
FoundWord(word='alure', locations=[Location(row=2, col=0), Location(row=1, col=1), Location(row=1, col=2), Location(row=0, col=2), Location(row=0, col=3)])
FoundWord(word='an', locations=[Location(row=2, col=0), Location(row=3, col=0)])
FoundWord(word='ant', locations=[Location(row=2, col=0), Location(row=3, col=0), Location(row=2, col=1)])
FoundWord(word='ante', locations=[Location(row=2, col=0), Location(row=3, col=0), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='anti', locations=[Location(row=2, col=0), Location(row=3, col=0), Location(row=2, col=1), Location(row=2, col=2)])
FoundWord(word='antic', locations=[Location(row=2, col=0), Location(row=3, col=0), Location(row=2, col=1), Location(row=2, col=2), Location(row=2, col=3)])
FoundWord(word='antre', locations=[Location(row=2, col=0), Location(row=3, col=0), Location(row=2, col=1), Location(row=3, col=1), Location(row=3, col=2)])
FoundWord(word='antrin', locations=[Location(row=2, col=0), Location(row=3, col=0), Location(row=2, col=1), Location(row=3, col=1), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='antu', locations=[Location(row=2, col=0), Location(row=3, col=0), Location(row=2, col=1), Location(row=1, col=2)])
FoundWord(word='ar', locations=[Location(row=2, col=0), Location(row=3, col=1)])
FoundWord(word='are', locations=[Location(row=2, col=0), Location(row=3, col=1), Location(row=3, col=2)])
FoundWord(word='aril', locations=[Location(row=2, col=0), Location(row=3, col=1), Location(row=2, col=2), Location(row=1, col=1)])
FoundWord(word='arise', locations=[Location(row=2, col=0), Location(row=3, col=1), Location(row=2, col=2), Location(row=1, col=3), Location(row=0, col=3)])
FoundWord(word='arite', locations=[Location(row=2, col=0), Location(row=3, col=1), Location(row=2, col=2), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='arius', locations=[Location(row=2, col=0), Location(row=3, col=1), Location(row=2, col=2), Location(row=1, col=2), Location(row=1, col=3)])
FoundWord(word='arn', locations=[Location(row=2, col=0), Location(row=3, col=1), Location(row=3, col=0)])
FoundWord(word='art', locations=[Location(row=2, col=0), Location(row=3, col=1), Location(row=2, col=1)])
FoundWord(word='artie', locations=[Location(row=2, col=0), Location(row=3, col=1), Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=2)])
FoundWord(word='as', locations=[Location(row=2, col=0), Location(row=1, col=0)])
FoundWord(word='ast', locations=[Location(row=2, col=0), Location(row=1, col=0), Location(row=2, col=1)])
FoundWord(word='aster', locations=[Location(row=2, col=0), Location(row=1, col=0), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='asterin', locations=[Location(row=2, col=0), Location(row=1, col=0), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='astern', locations=[Location(row=2, col=0), Location(row=1, col=0), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1), Location(row=3, col=0)])
FoundWord(word='astir', locations=[Location(row=2, col=0), Location(row=1, col=0), Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=1)])
FoundWord(word='astur', locations=[Location(row=2, col=0), Location(row=1, col=0), Location(row=2, col=1), Location(row=1, col=2), Location(row=0, col=2)])
FoundWord(word='at', locations=[Location(row=2, col=0), Location(row=2, col=1)])
FoundWord(word='ate', locations=[Location(row=2, col=0), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='aten', locations=[Location(row=2, col=0), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=3)])
FoundWord(word='ati', locations=[Location(row=2, col=0), Location(row=2, col=1), Location(row=2, col=2)])
FoundWord(word='atis', locations=[Location(row=2, col=0), Location(row=2, col=1), Location(row=2, col=2), Location(row=1, col=3)])
FoundWord(word='c', locations=[Location(row=2, col=3)])
FoundWord(word='ce', locations=[Location(row=2, col=3), Location(row=3, col=2)])
FoundWord(word='ceil', locations=[Location(row=2, col=3), Location(row=3, col=2), Location(row=2, col=2), Location(row=1, col=1)])
FoundWord(word='ceral', locations=[Location(row=2, col=3), Location(row=3, col=2), Location(row=3, col=1), Location(row=2, col=0), Location(row=1, col=1)])
FoundWord(word='ceras', locations=[Location(row=2, col=3), Location(row=3, col=2), Location(row=3, col=1), Location(row=2, col=0), Location(row=1, col=0)])
FoundWord(word='cerin', locations=[Location(row=2, col=3), Location(row=3, col=2), Location(row=3, col=1), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='cerise', locations=[Location(row=2, col=3), Location(row=3, col=2), Location(row=3, col=1), Location(row=2, col=2), Location(row=1, col=3), Location(row=0, col=3)])
FoundWord(word='cern', locations=[Location(row=2, col=3), Location(row=3, col=2), Location(row=3, col=1), Location(row=3, col=0)])
FoundWord(word='certis', locations=[Location(row=2, col=3), Location(row=3, col=2), Location(row=3, col=1), Location(row=2, col=1), Location(row=2, col=2), Location(row=1, col=3)])
FoundWord(word='ceti', locations=[Location(row=2, col=3), Location(row=3, col=2), Location(row=2, col=1), Location(row=2, col=2)])
FoundWord(word='cetin', locations=[Location(row=2, col=3), Location(row=3, col=2), Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='cetus', locations=[Location(row=2, col=3), Location(row=3, col=2), Location(row=2, col=1), Location(row=1, col=2), Location(row=1, col=3)])
FoundWord(word='cine', locations=[Location(row=2, col=3), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='cise', locations=[Location(row=2, col=3), Location(row=2, col=2), Location(row=1, col=3), Location(row=0, col=3)])
FoundWord(word='cit', locations=[Location(row=2, col=3), Location(row=2, col=2), Location(row=2, col=1)])
FoundWord(word='cite', locations=[Location(row=2, col=3), Location(row=2, col=2), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='citer', locations=[Location(row=2, col=3), Location(row=2, col=2), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='citral', locations=[Location(row=2, col=3), Location(row=2, col=2), Location(row=2, col=1), Location(row=3, col=1), Location(row=2, col=0), Location(row=1, col=1)])
FoundWord(word='cue', locations=[Location(row=2, col=3), Location(row=1, col=2), Location(row=0, col=3)])
FoundWord(word='cuir', locations=[Location(row=2, col=3), Location(row=1, col=2), Location(row=2, col=2), Location(row=3, col=1)])
FoundWord(word='cull', locations=[Location(row=2, col=3), Location(row=1, col=2), Location(row=1, col=1), Location(row=0, col=0)])
FoundWord(word='cult', locations=[Location(row=2, col=3), Location(row=1, col=2), Location(row=1, col=1), Location(row=2, col=1)])
FoundWord(word='cur', locations=[Location(row=2, col=3), Location(row=1, col=2), Location(row=0, col=2)])
FoundWord(word='cure', locations=[Location(row=2, col=3), Location(row=1, col=2), Location(row=0, col=2), Location(row=0, col=3)])
FoundWord(word='curl', locations=[Location(row=2, col=3), Location(row=1, col=2), Location(row=0, col=2), Location(row=1, col=1)])
FoundWord(word='curse', locations=[Location(row=2, col=3), Location(row=1, col=2), Location(row=0, col=2), Location(row=1, col=3), Location(row=0, col=3)])
FoundWord(word='cusie', locations=[Location(row=2, col=3), Location(row=1, col=2), Location(row=1, col=3), Location(row=2, col=2), Location(row=3, col=2)])
FoundWord(word='cut', locations=[Location(row=2, col=3), Location(row=1, col=2), Location(row=2, col=1)])
FoundWord(word='cute', locations=[Location(row=2, col=3), Location(row=1, col=2), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='cutie', locations=[Location(row=2, col=3), Location(row=1, col=2), Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=2)])
FoundWord(word='cutin', locations=[Location(row=2, col=3), Location(row=1, col=2), Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='cutis', locations=[Location(row=2, col=3), Location(row=1, col=2), Location(row=2, col=1), Location(row=2, col=2), Location(row=1, col=3)])
FoundWord(word='e', locations=[Location(row=0, col=3)])
FoundWord(word='e', locations=[Location(row=3, col=2)])
FoundWord(word='en', locations=[Location(row=3, col=2), Location(row=3, col=3)])
FoundWord(word='encurl', locations=[Location(row=3, col=2), Location(row=3, col=3), Location(row=2, col=3), Location(row=1, col=2), Location(row=0, col=2), Location(row=1, col=1)])
FoundWord(word='er', locations=[Location(row=0, col=3), Location(row=0, col=2)])
FoundWord(word='er', locations=[Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='era', locations=[Location(row=3, col=2), Location(row=3, col=1), Location(row=2, col=0)])
FoundWord(word='eral', locations=[Location(row=3, col=2), Location(row=3, col=1), Location(row=2, col=0), Location(row=1, col=1)])
FoundWord(word='erastus', locations=[Location(row=3, col=2), Location(row=3, col=1), Location(row=2, col=0), Location(row=1, col=0), Location(row=2, col=1), Location(row=1, col=2), Location(row=1, col=3)])
FoundWord(word='eric', locations=[Location(row=3, col=2), Location(row=3, col=1), Location(row=2, col=2), Location(row=2, col=3)])
FoundWord(word='ers', locations=[Location(row=0, col=3), Location(row=0, col=2), Location(row=1, col=3)])
FoundWord(word='eruc', locations=[Location(row=0, col=3), Location(row=0, col=2), Location(row=1, col=2), Location(row=2, col=3)])
FoundWord(word='erucin', locations=[Location(row=0, col=3), Location(row=0, col=2), Location(row=1, col=2), Location(row=2, col=3), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='es', locations=[Location(row=0, col=3), Location(row=1, col=3)])
FoundWord(word='esculin', locations=[Location(row=0, col=3), Location(row=1, col=3), Location(row=2, col=3), Location(row=1, col=2), Location(row=1, col=1), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='eta', locations=[Location(row=3, col=2), Location(row=2, col=1), Location(row=2, col=0)])
FoundWord(word='etna', locations=[Location(row=3, col=2), Location(row=2, col=1), Location(row=3, col=0), Location(row=2, col=0)])
FoundWord(word='etui', locations=[Location(row=3, col=2), Location(row=2, col=1), Location(row=1, col=2), Location(row=2, col=2)])
FoundWord(word='eu', locations=[Location(row=0, col=3), Location(row=1, col=2)])
FoundWord(word='i', locations=[Location(row=2, col=2)])
FoundWord(word='ice', locations=[Location(row=2, col=2), Location(row=2, col=3), Location(row=3, col=2)])
FoundWord(word='ie', locations=[Location(row=2, col=2), Location(row=3, col=2)])
FoundWord(word='ila', locations=[Location(row=2, col=2), Location(row=1, col=1), Location(row=2, col=0)])
FoundWord(word='ill', locations=[Location(row=2, col=2), Location(row=1, col=1), Location(row=0, col=0)])
FoundWord(word='in', locations=[Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='incult', locations=[Location(row=2, col=2), Location(row=3, col=3), Location(row=2, col=3), Location(row=1, col=2), Location(row=1, col=1), Location(row=2, col=1)])
FoundWord(word='incur', locations=[Location(row=2, col=2), Location(row=3, col=3), Location(row=2, col=3), Location(row=1, col=2), Location(row=0, col=2)])
FoundWord(word='incurse', locations=[Location(row=2, col=2), Location(row=3, col=3), Location(row=2, col=3), Location(row=1, col=2), Location(row=0, col=2), Location(row=1, col=3), Location(row=0, col=3)])
FoundWord(word='incus', locations=[Location(row=2, col=2), Location(row=3, col=3), Location(row=2, col=3), Location(row=1, col=2), Location(row=1, col=3)])
FoundWord(word='incuse', locations=[Location(row=2, col=2), Location(row=3, col=3), Location(row=2, col=3), Location(row=1, col=2), Location(row=1, col=3), Location(row=0, col=3)])
FoundWord(word='incut', locations=[Location(row=2, col=2), Location(row=3, col=3), Location(row=2, col=3), Location(row=1, col=2), Location(row=2, col=1)])
FoundWord(word='inert', locations=[Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2), Location(row=3, col=1), Location(row=2, col=1)])
FoundWord(word='ira', locations=[Location(row=2, col=2), Location(row=3, col=1), Location(row=2, col=0)])
FoundWord(word='iran', locations=[Location(row=2, col=2), Location(row=3, col=1), Location(row=2, col=0), Location(row=3, col=0)])
FoundWord(word='irate', locations=[Location(row=2, col=2), Location(row=3, col=1), Location(row=2, col=0), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='ire', locations=[Location(row=2, col=2), Location(row=3, col=1), Location(row=3, col=2)])
FoundWord(word='is', locations=[Location(row=2, col=2), Location(row=1, col=3)])
FoundWord(word='it', locations=[Location(row=2, col=2), Location(row=2, col=1)])
FoundWord(word='ita', locations=[Location(row=2, col=2), Location(row=2, col=1), Location(row=2, col=0)])
FoundWord(word='iten', locations=[Location(row=2, col=2), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=3)])
FoundWord(word='iter', locations=[Location(row=2, col=2), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='its', locations=[Location(row=2, col=2), Location(row=2, col=1), Location(row=1, col=0)])
FoundWord(word='l', locations=[Location(row=0, col=0)])
FoundWord(word='l', locations=[Location(row=1, col=1)])
FoundWord(word='la', locations=[Location(row=1, col=1), Location(row=2, col=0)])
FoundWord(word='lan', locations=[Location(row=1, col=1), Location(row=2, col=0), Location(row=3, col=0)])
FoundWord(word='lant', locations=[Location(row=1, col=1), Location(row=2, col=0), Location(row=3, col=0), Location(row=2, col=1)])
FoundWord(word='lar', locations=[Location(row=1, col=1), Location(row=2, col=0), Location(row=3, col=1)])
FoundWord(word='lari', locations=[Location(row=1, col=1), Location(row=2, col=0), Location(row=3, col=1), Location(row=2, col=2)])
FoundWord(word='larin', locations=[Location(row=1, col=1), Location(row=2, col=0), Location(row=3, col=1), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='larine', locations=[Location(row=1, col=1), Location(row=2, col=0), Location(row=3, col=1), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='las', locations=[Location(row=1, col=1), Location(row=2, col=0), Location(row=1, col=0)])
FoundWord(word='last', locations=[Location(row=1, col=1), Location(row=2, col=0), Location(row=1, col=0), Location(row=2, col=1)])
FoundWord(word='laster', locations=[Location(row=1, col=1), Location(row=2, col=0), Location(row=1, col=0), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='lastre', locations=[Location(row=1, col=1), Location(row=2, col=0), Location(row=1, col=0), Location(row=2, col=1), Location(row=3, col=1), Location(row=3, col=2)])
FoundWord(word='lat', locations=[Location(row=1, col=1), Location(row=2, col=0), Location(row=2, col=1)])
FoundWord(word='late', locations=[Location(row=1, col=1), Location(row=2, col=0), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='laten', locations=[Location(row=1, col=1), Location(row=2, col=0), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=3)])
FoundWord(word='later', locations=[Location(row=1, col=1), Location(row=2, col=0), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='latin', locations=[Location(row=1, col=1), Location(row=2, col=0), Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='latiner', locations=[Location(row=1, col=1), Location(row=2, col=0), Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='latrine', locations=[Location(row=1, col=1), Location(row=2, col=0), Location(row=2, col=1), Location(row=3, col=1), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='latris', locations=[Location(row=1, col=1), Location(row=2, col=0), Location(row=2, col=1), Location(row=3, col=1), Location(row=2, col=2), Location(row=1, col=3)])
FoundWord(word='latus', locations=[Location(row=1, col=1), Location(row=2, col=0), Location(row=2, col=1), Location(row=1, col=2), Location(row=1, col=3)])
FoundWord(word='li', locations=[Location(row=1, col=1), Location(row=2, col=2)])
FoundWord(word='lie', locations=[Location(row=1, col=1), Location(row=2, col=2), Location(row=3, col=2)])
FoundWord(word='lien', locations=[Location(row=1, col=1), Location(row=2, col=2), Location(row=3, col=2), Location(row=3, col=3)])
FoundWord(word='lier', locations=[Location(row=1, col=1), Location(row=2, col=2), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='lin', locations=[Location(row=1, col=1), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='line', locations=[Location(row=1, col=1), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='linecut', locations=[Location(row=1, col=1), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2), Location(row=2, col=3), Location(row=1, col=2), Location(row=2, col=1)])
FoundWord(word='liner', locations=[Location(row=1, col=1), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='linet', locations=[Location(row=1, col=1), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2), Location(row=2, col=1)])
FoundWord(word='lira', locations=[Location(row=1, col=1), Location(row=2, col=2), Location(row=3, col=1), Location(row=2, col=0)])
FoundWord(word='lirate', locations=[Location(row=1, col=1), Location(row=2, col=2), Location(row=3, col=1), Location(row=2, col=0), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='lire', locations=[Location(row=1, col=1), Location(row=2, col=2), Location(row=3, col=1), Location(row=3, col=2)])
FoundWord(word='lis', locations=[Location(row=1, col=1), Location(row=2, col=2), Location(row=1, col=3)])
FoundWord(word='lise', locations=[Location(row=1, col=1), Location(row=2, col=2), Location(row=1, col=3), Location(row=0, col=3)])
FoundWord(word='lit', locations=[Location(row=1, col=1), Location(row=2, col=2), Location(row=2, col=1)])
FoundWord(word='litas', locations=[Location(row=1, col=1), Location(row=2, col=2), Location(row=2, col=1), Location(row=2, col=0), Location(row=1, col=0)])
FoundWord(word='lite', locations=[Location(row=1, col=1), Location(row=2, col=2), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='liter', locations=[Location(row=1, col=1), Location(row=2, col=2), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='litra', locations=[Location(row=1, col=1), Location(row=2, col=2), Location(row=2, col=1), Location(row=3, col=1), Location(row=2, col=0)])
FoundWord(word='litus', locations=[Location(row=1, col=1), Location(row=2, col=2), Location(row=2, col=1), Location(row=1, col=2), Location(row=1, col=3)])
FoundWord(word='lu', locations=[Location(row=1, col=1), Location(row=1, col=2)])
FoundWord(word='luce', locations=[Location(row=1, col=1), Location(row=1, col=2), Location(row=2, col=3), Location(row=3, col=2)])
FoundWord(word='lucern', locations=[Location(row=1, col=1), Location(row=1, col=2), Location(row=2, col=3), Location(row=3, col=2), Location(row=3, col=1), Location(row=3, col=0)])
FoundWord(word='lucet', locations=[Location(row=1, col=1), Location(row=1, col=2), Location(row=2, col=3), Location(row=3, col=2), Location(row=2, col=1)])
FoundWord(word='lucite', locations=[Location(row=1, col=1), Location(row=1, col=2), Location(row=2, col=3), Location(row=2, col=2), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='lue', locations=[Location(row=1, col=1), Location(row=1, col=2), Location(row=0, col=3)])
FoundWord(word='lues', locations=[Location(row=1, col=1), Location(row=1, col=2), Location(row=0, col=3), Location(row=1, col=3)])
FoundWord(word='luite', locations=[Location(row=1, col=1), Location(row=1, col=2), Location(row=2, col=2), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='lur', locations=[Location(row=1, col=1), Location(row=1, col=2), Location(row=0, col=2)])
FoundWord(word='lure', locations=[Location(row=1, col=1), Location(row=1, col=2), Location(row=0, col=2), Location(row=0, col=3)])
FoundWord(word='lut', locations=[Location(row=1, col=1), Location(row=1, col=2), Location(row=2, col=1)])
FoundWord(word='lute', locations=[Location(row=1, col=1), Location(row=1, col=2), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='lutein', locations=[Location(row=1, col=1), Location(row=1, col=2), Location(row=2, col=1), Location(row=3, col=2), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='luter', locations=[Location(row=1, col=1), Location(row=1, col=2), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='lutra', locations=[Location(row=1, col=1), Location(row=1, col=2), Location(row=2, col=1), Location(row=3, col=1), Location(row=2, col=0)])
FoundWord(word='lutrin', locations=[Location(row=1, col=1), Location(row=1, col=2), Location(row=2, col=1), Location(row=3, col=1), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='lutrine', locations=[Location(row=1, col=1), Location(row=1, col=2), Location(row=2, col=1), Location(row=3, col=1), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='n', locations=[Location(row=3, col=0)])
FoundWord(word='n', locations=[Location(row=3, col=3)])
FoundWord(word='na', locations=[Location(row=3, col=0), Location(row=2, col=0)])
FoundWord(word='nar', locations=[Location(row=3, col=0), Location(row=2, col=0), Location(row=3, col=1)])
FoundWord(word='naric', locations=[Location(row=3, col=0), Location(row=2, col=0), Location(row=3, col=1), Location(row=2, col=2), Location(row=2, col=3)])
FoundWord(word='narine', locations=[Location(row=3, col=0), Location(row=2, col=0), Location(row=3, col=1), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='nast', locations=[Location(row=3, col=0), Location(row=2, col=0), Location(row=1, col=0), Location(row=2, col=1)])
FoundWord(word='nastic', locations=[Location(row=3, col=0), Location(row=2, col=0), Location(row=1, col=0), Location(row=2, col=1), Location(row=2, col=2), Location(row=2, col=3)])
FoundWord(word='nat', locations=[Location(row=3, col=0), Location(row=2, col=0), Location(row=2, col=1)])
FoundWord(word='natr', locations=[Location(row=3, col=0), Location(row=2, col=0), Location(row=2, col=1), Location(row=3, col=1)])
FoundWord(word='nature', locations=[Location(row=3, col=0), Location(row=2, col=0), Location(row=2, col=1), Location(row=1, col=2), Location(row=0, col=2), Location(row=0, col=3)])
FoundWord(word='ne', locations=[Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='nei', locations=[Location(row=3, col=3), Location(row=3, col=2), Location(row=2, col=2)])
FoundWord(word='neil', locations=[Location(row=3, col=3), Location(row=3, col=2), Location(row=2, col=2), Location(row=1, col=1)])
FoundWord(word='neri', locations=[Location(row=3, col=3), Location(row=3, col=2), Location(row=3, col=1), Location(row=2, col=2)])
FoundWord(word='nerita', locations=[Location(row=3, col=3), Location(row=3, col=2), Location(row=3, col=1), Location(row=2, col=2), Location(row=2, col=1), Location(row=2, col=0)])
FoundWord(word='net', locations=[Location(row=3, col=3), Location(row=3, col=2), Location(row=2, col=1)])
FoundWord(word='neti', locations=[Location(row=3, col=3), Location(row=3, col=2), Location(row=2, col=1), Location(row=2, col=2)])
FoundWord(word='ni', locations=[Location(row=3, col=3), Location(row=2, col=2)])
FoundWord(word='nice', locations=[Location(row=3, col=3), Location(row=2, col=2), Location(row=2, col=3), Location(row=3, col=2)])
FoundWord(word='nil', locations=[Location(row=3, col=3), Location(row=2, col=2), Location(row=1, col=1)])
FoundWord(word='nit', locations=[Location(row=3, col=3), Location(row=2, col=2), Location(row=2, col=1)])
FoundWord(word='niter', locations=[Location(row=3, col=3), Location(row=2, col=2), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='niue', locations=[Location(row=3, col=3), Location(row=2, col=2), Location(row=1, col=2), Location(row=0, col=3)])
FoundWord(word='r', locations=[Location(row=0, col=2)])
FoundWord(word='r', locations=[Location(row=3, col=1)])
FoundWord(word='ra', locations=[Location(row=3, col=1), Location(row=2, col=0)])
FoundWord(word='ran', locations=[Location(row=3, col=1), Location(row=2, col=0), Location(row=3, col=0)])
FoundWord(word='rant', locations=[Location(row=3, col=1), Location(row=2, col=0), Location(row=3, col=0), Location(row=2, col=1)])
FoundWord(word='ras', locations=[Location(row=3, col=1), Location(row=2, col=0), Location(row=1, col=0)])
FoundWord(word='rastus', locations=[Location(row=3, col=1), Location(row=2, col=0), Location(row=1, col=0), Location(row=2, col=1), Location(row=1, col=2), Location(row=1, col=3)])
FoundWord(word='rat', locations=[Location(row=3, col=1), Location(row=2, col=0), Location(row=2, col=1)])
FoundWord(word='rate', locations=[Location(row=3, col=1), Location(row=2, col=0), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='ratine', locations=[Location(row=3, col=1), Location(row=2, col=0), Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='ratline', locations=[Location(row=3, col=1), Location(row=2, col=0), Location(row=2, col=1), Location(row=1, col=1), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='re', locations=[Location(row=0, col=2), Location(row=0, col=3)])
FoundWord(word='re', locations=[Location(row=3, col=1), Location(row=3, col=2)])
FoundWord(word='recital', locations=[Location(row=3, col=1), Location(row=3, col=2), Location(row=2, col=3), Location(row=2, col=2), Location(row=2, col=1), Location(row=2, col=0), Location(row=1, col=1)])
FoundWord(word='recur', locations=[Location(row=3, col=1), Location(row=3, col=2), Location(row=2, col=3), Location(row=1, col=2), Location(row=0, col=2)])
FoundWord(word='recure', locations=[Location(row=3, col=1), Location(row=3, col=2), Location(row=2, col=3), Location(row=1, col=2), Location(row=0, col=2), Location(row=0, col=3)])
FoundWord(word='recurl', locations=[Location(row=3, col=1), Location(row=3, col=2), Location(row=2, col=3), Location(row=1, col=2), Location(row=0, col=2), Location(row=1, col=1)])
FoundWord(word='recurse', locations=[Location(row=3, col=1), Location(row=3, col=2), Location(row=2, col=3), Location(row=1, col=2), Location(row=0, col=2), Location(row=1, col=3), Location(row=0, col=3)])
FoundWord(word='recuse', locations=[Location(row=3, col=1), Location(row=3, col=2), Location(row=2, col=3), Location(row=1, col=2), Location(row=1, col=3), Location(row=0, col=3)])
FoundWord(word='recut', locations=[Location(row=3, col=1), Location(row=3, col=2), Location(row=2, col=3), Location(row=1, col=2), Location(row=2, col=1)])
FoundWord(word='rein', locations=[Location(row=3, col=1), Location(row=3, col=2), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='reincur', locations=[Location(row=3, col=1), Location(row=3, col=2), Location(row=2, col=2), Location(row=3, col=3), Location(row=2, col=3), Location(row=1, col=2), Location(row=0, col=2)])
FoundWord(word='reis', locations=[Location(row=3, col=1), Location(row=3, col=2), Location(row=2, col=2), Location(row=1, col=3)])
FoundWord(word='reit', locations=[Location(row=3, col=1), Location(row=3, col=2), Location(row=2, col=2), Location(row=2, col=1)])
FoundWord(word='resin', locations=[Location(row=0, col=2), Location(row=0, col=3), Location(row=1, col=3), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='resiner', locations=[Location(row=0, col=2), Location(row=0, col=3), Location(row=1, col=3), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='resuit', locations=[Location(row=0, col=2), Location(row=0, col=3), Location(row=1, col=3), Location(row=1, col=2), Location(row=2, col=2), Location(row=2, col=1)])
FoundWord(word='result', locations=[Location(row=0, col=2), Location(row=0, col=3), Location(row=1, col=3), Location(row=1, col=2), Location(row=1, col=1), Location(row=2, col=1)])
FoundWord(word='ret', locations=[Location(row=3, col=1), Location(row=3, col=2), Location(row=2, col=1)])
FoundWord(word='retan', locations=[Location(row=3, col=1), Location(row=3, col=2), Location(row=2, col=1), Location(row=2, col=0), Location(row=3, col=0)])
FoundWord(word='reticula', locations=[Location(row=3, col=1), Location(row=3, col=2), Location(row=2, col=1), Location(row=2, col=2), Location(row=2, col=3), Location(row=1, col=2), Location(row=1, col=1), Location(row=2, col=0)])
FoundWord(word='retill', locations=[Location(row=3, col=1), Location(row=3, col=2), Location(row=2, col=1), Location(row=2, col=2), Location(row=1, col=1), Location(row=0, col=0)])
FoundWord(word='retin', locations=[Location(row=3, col=1), Location(row=3, col=2), Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='retuse', locations=[Location(row=3, col=1), Location(row=3, col=2), Location(row=2, col=1), Location(row=1, col=2), Location(row=1, col=3), Location(row=0, col=3)])
FoundWord(word='rice', locations=[Location(row=3, col=1), Location(row=2, col=2), Location(row=2, col=3), Location(row=3, col=2)])
FoundWord(word='rie', locations=[Location(row=3, col=1), Location(row=2, col=2), Location(row=3, col=2)])
FoundWord(word='rill', locations=[Location(row=3, col=1), Location(row=2, col=2), Location(row=1, col=1), Location(row=0, col=0)])
FoundWord(word='rine', locations=[Location(row=3, col=1), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='rise', locations=[Location(row=3, col=1), Location(row=2, col=2), Location(row=1, col=3), Location(row=0, col=3)])
FoundWord(word='riser', locations=[Location(row=3, col=1), Location(row=2, col=2), Location(row=1, col=3), Location(row=0, col=3), Location(row=0, col=2)])
FoundWord(word='rit', locations=[Location(row=3, col=1), Location(row=2, col=2), Location(row=2, col=1)])
FoundWord(word='rita', locations=[Location(row=3, col=1), Location(row=2, col=2), Location(row=2, col=1), Location(row=2, col=0)])
FoundWord(word='rite', locations=[Location(row=3, col=1), Location(row=2, col=2), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='rue', locations=[Location(row=0, col=2), Location(row=1, col=2), Location(row=0, col=3)])
FoundWord(word='ruin', locations=[Location(row=0, col=2), Location(row=1, col=2), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='ruiner', locations=[Location(row=0, col=2), Location(row=1, col=2), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='rull', locations=[Location(row=0, col=2), Location(row=1, col=2), Location(row=1, col=1), Location(row=0, col=0)])
FoundWord(word='rus', locations=[Location(row=0, col=2), Location(row=1, col=2), Location(row=1, col=3)])
FoundWord(word='ruse', locations=[Location(row=0, col=2), Location(row=1, col=2), Location(row=1, col=3), Location(row=0, col=3)])
FoundWord(word='rusin', locations=[Location(row=0, col=2), Location(row=1, col=2), Location(row=1, col=3), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='rusine', locations=[Location(row=0, col=2), Location(row=1, col=2), Location(row=1, col=3), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='rut', locations=[Location(row=0, col=2), Location(row=1, col=2), Location(row=2, col=1)])
FoundWord(word='ruta', locations=[Location(row=0, col=2), Location(row=1, col=2), Location(row=2, col=1), Location(row=2, col=0)])
FoundWord(word='rutic', locations=[Location(row=0, col=2), Location(row=1, col=2), Location(row=2, col=1), Location(row=2, col=2), Location(row=2, col=3)])
FoundWord(word='rutin', locations=[Location(row=0, col=2), Location(row=1, col=2), Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='s', locations=[Location(row=1, col=0)])
FoundWord(word='s', locations=[Location(row=1, col=3)])
FoundWord(word='sa', locations=[Location(row=1, col=0), Location(row=2, col=0)])
FoundWord(word='sal', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=1, col=1)])
FoundWord(word='salic', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=2), Location(row=2, col=3)])
FoundWord(word='saline', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='salite', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=2), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='salt', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=1)])
FoundWord(word='salten', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=3)])
FoundWord(word='salter', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='saltern', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1), Location(row=3, col=0)])
FoundWord(word='saltier', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='saltine', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='saltus', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=1), Location(row=1, col=2), Location(row=1, col=3)])
FoundWord(word='salute', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=1, col=1), Location(row=1, col=2), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='saluter', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=1, col=1), Location(row=1, col=2), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='san', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=3, col=0)])
FoundWord(word='sant', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=3, col=0), Location(row=2, col=1)])
FoundWord(word='santir', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=3, col=0), Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=1)])
FoundWord(word='sar', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=3, col=1)])
FoundWord(word='sare', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=3, col=1), Location(row=3, col=2)])
FoundWord(word='sari', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=3, col=1), Location(row=2, col=2)])
FoundWord(word='sart', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=3, col=1), Location(row=2, col=1)])
FoundWord(word='sat', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=2, col=1)])
FoundWord(word='sate', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='satin', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='satine', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='satire', locations=[Location(row=1, col=0), Location(row=2, col=0), Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=1), Location(row=3, col=2)])
FoundWord(word='scull', locations=[Location(row=1, col=3), Location(row=2, col=3), Location(row=1, col=2), Location(row=1, col=1), Location(row=0, col=0)])
FoundWord(word='scur', locations=[Location(row=1, col=3), Location(row=2, col=3), Location(row=1, col=2), Location(row=0, col=2)])
FoundWord(word='scut', locations=[Location(row=1, col=3), Location(row=2, col=3), Location(row=1, col=2), Location(row=2, col=1)])
FoundWord(word='scuta', locations=[Location(row=1, col=3), Location(row=2, col=3), Location(row=1, col=2), Location(row=2, col=1), Location(row=2, col=0)])
FoundWord(word='scutal', locations=[Location(row=1, col=3), Location(row=2, col=3), Location(row=1, col=2), Location(row=2, col=1), Location(row=2, col=0), Location(row=1, col=1)])
FoundWord(word='scute', locations=[Location(row=1, col=3), Location(row=2, col=3), Location(row=1, col=2), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='se', locations=[Location(row=1, col=3), Location(row=0, col=3)])
FoundWord(word='ser', locations=[Location(row=1, col=3), Location(row=0, col=3), Location(row=0, col=2)])
FoundWord(word='serut', locations=[Location(row=1, col=3), Location(row=0, col=3), Location(row=0, col=2), Location(row=1, col=2), Location(row=2, col=1)])
FoundWord(word='si', locations=[Location(row=1, col=3), Location(row=2, col=2)])
FoundWord(word='sic', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=2, col=3)])
FoundWord(word='sice', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=2, col=3), Location(row=3, col=2)])
FoundWord(word='sicula', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=2, col=3), Location(row=1, col=2), Location(row=1, col=1), Location(row=2, col=0)])
FoundWord(word='sicular', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=2, col=3), Location(row=1, col=2), Location(row=1, col=1), Location(row=2, col=0), Location(row=3, col=1)])
FoundWord(word='sie', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=3, col=2)])
FoundWord(word='sier', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='sil', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=1, col=1)])
FoundWord(word='silas', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=1, col=1), Location(row=2, col=0), Location(row=1, col=0)])
FoundWord(word='sill', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=1, col=1), Location(row=0, col=0)])
FoundWord(word='silt', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=1, col=1), Location(row=2, col=1)])
FoundWord(word='sin', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='since', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=3, col=3), Location(row=2, col=3), Location(row=3, col=2)])
FoundWord(word='sine', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='sinecure', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2), Location(row=2, col=3), Location(row=1, col=2), Location(row=0, col=2), Location(row=0, col=3)])
FoundWord(word='sir', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=3, col=1)])
FoundWord(word='sire', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=3, col=1), Location(row=3, col=2)])
FoundWord(word='siren', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=3, col=1), Location(row=3, col=2), Location(row=3, col=3)])
FoundWord(word='sit', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=2, col=1)])
FoundWord(word='sita', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=2, col=1), Location(row=2, col=0)])
FoundWord(word='sitar', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=2, col=1), Location(row=2, col=0), Location(row=3, col=1)])
FoundWord(word='site', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='situla', locations=[Location(row=1, col=3), Location(row=2, col=2), Location(row=2, col=1), Location(row=1, col=2), Location(row=1, col=1), Location(row=2, col=0)])
FoundWord(word='sla', locations=[Location(row=1, col=0), Location(row=1, col=1), Location(row=2, col=0)])
FoundWord(word='slant', locations=[Location(row=1, col=0), Location(row=1, col=1), Location(row=2, col=0), Location(row=3, col=0), Location(row=2, col=1)])
FoundWord(word='slare', locations=[Location(row=1, col=0), Location(row=1, col=1), Location(row=2, col=0), Location(row=3, col=1), Location(row=3, col=2)])
FoundWord(word='slart', locations=[Location(row=1, col=0), Location(row=1, col=1), Location(row=2, col=0), Location(row=3, col=1), Location(row=2, col=1)])
FoundWord(word='slat', locations=[Location(row=1, col=0), Location(row=1, col=1), Location(row=2, col=0), Location(row=2, col=1)])
FoundWord(word='slate', locations=[Location(row=1, col=0), Location(row=1, col=1), Location(row=2, col=0), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='slater', locations=[Location(row=1, col=0), Location(row=1, col=1), Location(row=2, col=0), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='slice', locations=[Location(row=1, col=0), Location(row=1, col=1), Location(row=2, col=2), Location(row=2, col=3), Location(row=3, col=2)])
FoundWord(word='slicer', locations=[Location(row=1, col=0), Location(row=1, col=1), Location(row=2, col=2), Location(row=2, col=3), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='sline', locations=[Location(row=1, col=0), Location(row=1, col=1), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='slirt', locations=[Location(row=1, col=0), Location(row=1, col=1), Location(row=2, col=2), Location(row=3, col=1), Location(row=2, col=1)])
FoundWord(word='slit', locations=[Location(row=1, col=0), Location(row=1, col=1), Location(row=2, col=2), Location(row=2, col=1)])
FoundWord(word='slite', locations=[Location(row=1, col=0), Location(row=1, col=1), Location(row=2, col=2), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='slue', locations=[Location(row=1, col=0), Location(row=1, col=1), Location(row=1, col=2), Location(row=0, col=3)])
FoundWord(word='sluer', locations=[Location(row=1, col=0), Location(row=1, col=1), Location(row=1, col=2), Location(row=0, col=3), Location(row=0, col=2)])
FoundWord(word='sluice', locations=[Location(row=1, col=0), Location(row=1, col=1), Location(row=1, col=2), Location(row=2, col=2), Location(row=2, col=3), Location(row=3, col=2)])
FoundWord(word='sluicer', locations=[Location(row=1, col=0), Location(row=1, col=1), Location(row=1, col=2), Location(row=2, col=2), Location(row=2, col=3), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='sluit', locations=[Location(row=1, col=0), Location(row=1, col=1), Location(row=1, col=2), Location(row=2, col=2), Location(row=2, col=1)])
FoundWord(word='slur', locations=[Location(row=1, col=0), Location(row=1, col=1), Location(row=1, col=2), Location(row=0, col=2)])
FoundWord(word='slut', locations=[Location(row=1, col=0), Location(row=1, col=1), Location(row=1, col=2), Location(row=2, col=1)])
FoundWord(word='sruti', locations=[Location(row=1, col=3), Location(row=0, col=2), Location(row=1, col=2), Location(row=2, col=1), Location(row=2, col=2)])
FoundWord(word='st', locations=[Location(row=1, col=0), Location(row=2, col=1)])
FoundWord(word='stall', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=2, col=0), Location(row=1, col=1), Location(row=0, col=0)])
FoundWord(word='star', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=2, col=0), Location(row=3, col=1)])
FoundWord(word='stare', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=2, col=0), Location(row=3, col=1), Location(row=3, col=2)])
FoundWord(word='starn', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=2, col=0), Location(row=3, col=1), Location(row=3, col=0)])
FoundWord(word='stein', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=3, col=2), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='sten', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=3)])
FoundWord(word='stencil', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=3), Location(row=2, col=3), Location(row=2, col=2), Location(row=1, col=1)])
FoundWord(word='steri', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1), Location(row=2, col=2)])
FoundWord(word='steric', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1), Location(row=2, col=2), Location(row=2, col=3)])
FoundWord(word='sterics', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1), Location(row=2, col=2), Location(row=2, col=3), Location(row=1, col=3)])
FoundWord(word='sterin', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='stern', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1), Location(row=3, col=0)])
FoundWord(word='sterna', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1), Location(row=3, col=0), Location(row=2, col=0)])
FoundWord(word='sternal', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1), Location(row=3, col=0), Location(row=2, col=0), Location(row=1, col=1)])
FoundWord(word='sternalis', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1), Location(row=3, col=0), Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=2), Location(row=1, col=3)])
FoundWord(word='still', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=2, col=2), Location(row=1, col=1), Location(row=0, col=0)])
FoundWord(word='stine', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='stir', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=1)])
FoundWord(word='stra', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=3, col=1), Location(row=2, col=0)])
FoundWord(word='stre', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=3, col=1), Location(row=3, col=2)])
FoundWord(word='stue', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=1, col=2), Location(row=0, col=3)])
FoundWord(word='stull', locations=[Location(row=1, col=0), Location(row=2, col=1), Location(row=1, col=2), Location(row=1, col=1), Location(row=0, col=0)])
FoundWord(word='sue', locations=[Location(row=1, col=3), Location(row=1, col=2), Location(row=0, col=3)])
FoundWord(word='suer', locations=[Location(row=1, col=3), Location(row=1, col=2), Location(row=0, col=3), Location(row=0, col=2)])
FoundWord(word='sui', locations=[Location(row=1, col=3), Location(row=1, col=2), Location(row=2, col=2)])
FoundWord(word='suine', locations=[Location(row=1, col=3), Location(row=1, col=2), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='suit', locations=[Location(row=1, col=3), Location(row=1, col=2), Location(row=2, col=2), Location(row=2, col=1)])
FoundWord(word='suite', locations=[Location(row=1, col=3), Location(row=1, col=2), Location(row=2, col=2), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='sula', locations=[Location(row=1, col=3), Location(row=1, col=2), Location(row=1, col=1), Location(row=2, col=0)])
FoundWord(word='sull', locations=[Location(row=1, col=3), Location(row=1, col=2), Location(row=1, col=1), Location(row=0, col=0)])
FoundWord(word='sultan', locations=[Location(row=1, col=3), Location(row=1, col=2), Location(row=1, col=1), Location(row=2, col=1), Location(row=2, col=0), Location(row=3, col=0)])
FoundWord(word='sur', locations=[Location(row=1, col=3), Location(row=1, col=2), Location(row=0, col=2)])
FoundWord(word='sure', locations=[Location(row=1, col=3), Location(row=1, col=2), Location(row=0, col=2), Location(row=0, col=3)])
FoundWord(word='sutra', locations=[Location(row=1, col=3), Location(row=1, col=2), Location(row=2, col=1), Location(row=3, col=1), Location(row=2, col=0)])
FoundWord(word='t', locations=[Location(row=2, col=1)])
FoundWord(word='ta', locations=[Location(row=2, col=1), Location(row=2, col=0)])
FoundWord(word='tal', locations=[Location(row=2, col=1), Location(row=2, col=0), Location(row=1, col=1)])
FoundWord(word='tali', locations=[Location(row=2, col=1), Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=2)])
FoundWord(word='talis', locations=[Location(row=2, col=1), Location(row=2, col=0), Location(row=1, col=1), Location(row=2, col=2), Location(row=1, col=3)])
FoundWord(word='tall', locations=[Location(row=2, col=1), Location(row=2, col=0), Location(row=1, col=1), Location(row=0, col=0)])
FoundWord(word='talus', locations=[Location(row=2, col=1), Location(row=2, col=0), Location(row=1, col=1), Location(row=1, col=2), Location(row=1, col=3)])
FoundWord(word='tan', locations=[Location(row=2, col=1), Location(row=2, col=0), Location(row=3, col=0)])
FoundWord(word='tanrec', locations=[Location(row=2, col=1), Location(row=2, col=0), Location(row=3, col=0), Location(row=3, col=1), Location(row=3, col=2), Location(row=2, col=3)])
FoundWord(word='tar', locations=[Location(row=2, col=1), Location(row=2, col=0), Location(row=3, col=1)])
FoundWord(word='tare', locations=[Location(row=2, col=1), Location(row=2, col=0), Location(row=3, col=1), Location(row=3, col=2)])
FoundWord(word='tari', locations=[Location(row=2, col=1), Location(row=2, col=0), Location(row=3, col=1), Location(row=2, col=2)])
FoundWord(word='tarie', locations=[Location(row=2, col=1), Location(row=2, col=0), Location(row=3, col=1), Location(row=2, col=2), Location(row=3, col=2)])
FoundWord(word='tarin', locations=[Location(row=2, col=1), Location(row=2, col=0), Location(row=3, col=1), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='tarn', locations=[Location(row=2, col=1), Location(row=2, col=0), Location(row=3, col=1), Location(row=3, col=0)])
FoundWord(word='te', locations=[Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='tec', locations=[Location(row=2, col=1), Location(row=3, col=2), Location(row=2, col=3)])
FoundWord(word='teil', locations=[Location(row=2, col=1), Location(row=3, col=2), Location(row=2, col=2), Location(row=1, col=1)])
FoundWord(word='ten', locations=[Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=3)])
FoundWord(word='tera', locations=[Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1), Location(row=2, col=0)])
FoundWord(word='teras', locations=[Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1), Location(row=2, col=0), Location(row=1, col=0)])
FoundWord(word='tern', locations=[Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1), Location(row=3, col=0)])
FoundWord(word='terna', locations=[Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1), Location(row=3, col=0), Location(row=2, col=0)])
FoundWord(word='ternal', locations=[Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1), Location(row=3, col=0), Location(row=2, col=0), Location(row=1, col=1)])
FoundWord(word='ti', locations=[Location(row=2, col=1), Location(row=2, col=2)])
FoundWord(word='tic', locations=[Location(row=2, col=1), Location(row=2, col=2), Location(row=2, col=3)])
FoundWord(word='tice', locations=[Location(row=2, col=1), Location(row=2, col=2), Location(row=2, col=3), Location(row=3, col=2)])
FoundWord(word='ticer', locations=[Location(row=2, col=1), Location(row=2, col=2), Location(row=2, col=3), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='ticul', locations=[Location(row=2, col=1), Location(row=2, col=2), Location(row=2, col=3), Location(row=1, col=2), Location(row=1, col=1)])
FoundWord(word='tie', locations=[Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=2)])
FoundWord(word='tien', locations=[Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=2), Location(row=3, col=3)])
FoundWord(word='tier', locations=[Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='til', locations=[Location(row=2, col=1), Location(row=2, col=2), Location(row=1, col=1)])
FoundWord(word='till', locations=[Location(row=2, col=1), Location(row=2, col=2), Location(row=1, col=1), Location(row=0, col=0)])
FoundWord(word='tin', locations=[Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='tine', locations=[Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='tire', locations=[Location(row=2, col=1), Location(row=2, col=2), Location(row=3, col=1), Location(row=3, col=2)])
FoundWord(word='tra', locations=[Location(row=2, col=1), Location(row=3, col=1), Location(row=2, col=0)])
FoundWord(word='tri', locations=[Location(row=2, col=1), Location(row=3, col=1), Location(row=2, col=2)])
FoundWord(word='trice', locations=[Location(row=2, col=1), Location(row=3, col=1), Location(row=2, col=2), Location(row=2, col=3), Location(row=3, col=2)])
FoundWord(word='trill', locations=[Location(row=2, col=1), Location(row=3, col=1), Location(row=2, col=2), Location(row=1, col=1), Location(row=0, col=0)])
FoundWord(word='trin', locations=[Location(row=2, col=1), Location(row=3, col=1), Location(row=2, col=2), Location(row=3, col=3)])
FoundWord(word='trine', locations=[Location(row=2, col=1), Location(row=3, col=1), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='trisul', locations=[Location(row=2, col=1), Location(row=3, col=1), Location(row=2, col=2), Location(row=1, col=3), Location(row=1, col=2), Location(row=1, col=1)])
FoundWord(word='trisula', locations=[Location(row=2, col=1), Location(row=3, col=1), Location(row=2, col=2), Location(row=1, col=3), Location(row=1, col=2), Location(row=1, col=1), Location(row=2, col=0)])
FoundWord(word='tsar', locations=[Location(row=2, col=1), Location(row=1, col=0), Location(row=2, col=0), Location(row=3, col=1)])
FoundWord(word='tu', locations=[Location(row=2, col=1), Location(row=1, col=2)])
FoundWord(word='tue', locations=[Location(row=2, col=1), Location(row=1, col=2), Location(row=0, col=3)])
FoundWord(word='tui', locations=[Location(row=2, col=1), Location(row=1, col=2), Location(row=2, col=2)])
FoundWord(word='tula', locations=[Location(row=2, col=1), Location(row=1, col=2), Location(row=1, col=1), Location(row=2, col=0)])
FoundWord(word='tulare', locations=[Location(row=2, col=1), Location(row=1, col=2), Location(row=1, col=1), Location(row=2, col=0), Location(row=3, col=1), Location(row=3, col=2)])
FoundWord(word='tur', locations=[Location(row=2, col=1), Location(row=1, col=2), Location(row=0, col=2)])
FoundWord(word='turse', locations=[Location(row=2, col=1), Location(row=1, col=2), Location(row=0, col=2), Location(row=1, col=3), Location(row=0, col=3)])
FoundWord(word='u', locations=[Location(row=1, col=2)])
FoundWord(word='ula', locations=[Location(row=1, col=2), Location(row=1, col=1), Location(row=2, col=0)])
FoundWord(word='ull', locations=[Location(row=1, col=2), Location(row=1, col=1), Location(row=0, col=0)])
FoundWord(word='ulster', locations=[Location(row=1, col=2), Location(row=1, col=1), Location(row=1, col=0), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1)])
FoundWord(word='ultra', locations=[Location(row=1, col=2), Location(row=1, col=1), Location(row=2, col=1), Location(row=3, col=1), Location(row=2, col=0)])
FoundWord(word='ur', locations=[Location(row=1, col=2), Location(row=0, col=2)])
FoundWord(word='ure', locations=[Location(row=1, col=2), Location(row=0, col=2), Location(row=0, col=3)])
FoundWord(word='urlar', locations=[Location(row=1, col=2), Location(row=0, col=2), Location(row=1, col=1), Location(row=2, col=0), Location(row=3, col=1)])
FoundWord(word='ursine', locations=[Location(row=1, col=2), Location(row=0, col=2), Location(row=1, col=3), Location(row=2, col=2), Location(row=3, col=3), Location(row=3, col=2)])
FoundWord(word='us', locations=[Location(row=1, col=2), Location(row=1, col=3)])
FoundWord(word='use', locations=[Location(row=1, col=2), Location(row=1, col=3), Location(row=0, col=3)])
FoundWord(word='user', locations=[Location(row=1, col=2), Location(row=1, col=3), Location(row=0, col=3), Location(row=0, col=2)])
FoundWord(word='ut', locations=[Location(row=1, col=2), Location(row=2, col=1)])
FoundWord(word='uta', locations=[Location(row=1, col=2), Location(row=2, col=1), Location(row=2, col=0)])
FoundWord(word='utas', locations=[Location(row=1, col=2), Location(row=2, col=1), Location(row=2, col=0), Location(row=1, col=0)])
FoundWord(word='ute', locations=[Location(row=1, col=2), Location(row=2, col=1), Location(row=3, col=2)])
FoundWord(word='uteri', locations=[Location(row=1, col=2), Location(row=2, col=1), Location(row=3, col=2), Location(row=3, col=1), Location(row=2, col=2)])
a
al
alice
alien
alin
aline
alit
alite
alt
alter
altern
altin
alur
alure
an
ant
ante
anti
antic
antre
antrin
antu
ar
are
aril
arise
arite
arius
arn
art
artie
as
ast
aster
asterin
astern
astir
astur
at
ate
aten
ati
atis
c
ce
ceil
ceral
ceras
cerin
cerise
cern
certis
ceti
cetin
cetus
cine
cise
cit
cite
citer
citral
cue
cuir
cull
cult
cur
cure
curl
curse
cusie
cut
cute
cutie
cutin
cutis
e
en
encurl
er
era
eral
erastus
eric
ers
eruc
erucin
es
esculin
eta
etna
etui
eu
i
ice
ie
ila
ill
in
incult
incur
incurse
incus
incuse
incut
inert
ira
iran
irate
ire
is
it
ita
iten
iter
its
l
la
lan
lant
lar
lari
larin
larine
las
last
laster
lastre
lat
late
laten
later
latin
latiner
latrine
latris
latus
li
lie
lien
lier
lin
line
linecut
liner
linet
lira
lirate
lire
lis
lise
lit
litas
lite
liter
litra
litus
lu
luce
lucern
lucet
lucite
lue
lues
luite
lur
lure
lut
lute
lutein
luter
lutra
lutrin
lutrine
n
na
nar
naric
narine
nast
nastic
nat
natr
nature
ne
nei
neil
neri
nerita
net
neti
ni
nice
nil
nit
niter
niue
r
ra
ran
rant
ras
rastus
rat
rate
ratine
ratline
re
recital
recur
recure
recurl
recurse
recuse
recut
rein
reincur
reis
reit
resin
resiner
resuit
result
ret
retan
reticula
retill
retin
retuse
rice
rie
rill
rine
rise
riser
rit
rita
rite
rue
ruin
ruiner
rull
rus
ruse
rusin
rusine
rut
ruta
rutic
rutin
s
sa
sal
salic
saline
salite
salt
salten
salter
saltern
saltier
saltine
saltus
salute
saluter
san
sant
santir
sar
sare
sari
sart
sat
sate
satin
satine
satire
scull
scur
scut
scuta
scutal
scute
se
ser
serut
si
sic
sice
sicula
sicular
sie
sier
sil
silas
sill
silt
sin
since
sine
sinecure
sir
sire
siren
sit
sita
sitar
site
situla
sla
slant
slare
slart
slat
slate
slater
slice
slicer
sline
slirt
slit
slite
slue
sluer
sluice
sluicer
sluit
slur
slut
sruti
st
stall
star
stare
starn
stein
sten
stencil
steri
steric
sterics
sterin
stern
sterna
sternal
sternalis
still
stine
stir
stra
stre
stue
stull
sue
suer
sui
suine
suit
suite
sula
sull
sultan
sur
sure
sutra
t
ta
tal
tali
talis
tall
talus
tan
tanrec
tar
tare
tari
tarie
tarin
tarn
te
tec
teil
ten
tera
teras
tern
terna
ternal
ti
tic
tice
ticer
ticul
tie
tien
tier
til
till
tin
tine
tire
tra
tri
trice
trill
trin
trine
trisul
trisula
tsar
tu
tue
tui
tula
tulare
tur
turse
u
ula
ull
ulster
ultra
ur
ure
urlar
ursine
us
use
user
ut
uta
utas
ute
uteri
import abc
from abc import ABCMeta
from collections import namedtuple
import bisect
import datetime
import pickle
import random
import string
import sys
import bloom_filter
import trie
"""
Solves Boggle/Scramble with Friends.
"""
TOKENS = ['a','b','c','d','e','f','g','h','j','k','l','m','n','o','p','qu','r','s','t','u','v','w','x','y','z']
DEBUG = False
# If true, will quit the search early when we know that no valid word starts
# with this prefix. For instance, the search for 'qr' would be abandoned
# immediately because no word starts with 'qr'.
PREFIX_PRUNE = True
TIMING_TEST = True
class Location(namedtuple('Location', ['row', 'col'])):
"""Represents a location on the board."""
def Adjacent(self):
"""Returns the 8 adjacent locations to this one."""
locs = []
for row_offset in [-1, 0, 1]:
for col_offset in [-1, 0, 1]:
# 0, 0 would be the current location and that's not adjacent
if row_offset != 0 or col_offset != 0:
locs.append(Location(self.row + row_offset, self.col + col_offset))
assert len(locs) == 8
return locs
# Represents a discovered word on the board, including the path taken to create it.
FoundWord = namedtuple('FoundWord', ['word', 'locations'])
# TODO(ndunn): Is this board class even necessary
class Board(object):
"""Represents a board, a two dimensional grid of tiles."""
def __init__(self, num_rows=4, num_cols=4):
self.num_rows = num_rows
self.num_cols = num_cols
self.board = []
for i in range(num_rows):
self.board.append([random.choice(TOKENS) for x in range(num_cols)])
def __repr__(self):
return repr(self.board)
def __str__(self):
return '\n'.join([str(row) for row in self.board])
def __getitem__(self, key):
"""Allow the board to be indexed."""
return self.board.__getitem__(key)
def IsValidLocation(self, location):
row_valid = location.row >= 0 and location.row < self.num_rows
col_valid = location.col >= 0 and location.col < self.num_cols
return row_valid and col_valid
class BoardSolver(object):
__metaclass__ = ABCMeta
@abc.abstractmethod
def HasPrefix(self, prefix):
pass
@abc.abstractmethod
def IsWord(self, prefix):
pass
def Solve(self, board):
"""Returns a list of FoundWord objects."""
solutions = []
# Start an exhaustive search of the board
for row in range(board.num_rows):
for col in range(board.num_cols):
loc = Location(row, col)
previous_locs = []
solutions.extend(self.DoSolve(board, previous_locs, loc, ''))
return solutions
def DoSolve(self, board, previous_locations, location, word_prefix):
"""Returns iterable of FoundWord objects.
Args:
previous_locations: a list of already visited locations
location: the current Location from where to start searching
word_prefix: the current word built up so far, as a string
"""
solutions = []
new_word = word_prefix + board[location.row][location.col]
previous_locations.append(location)
if PREFIX_PRUNE and not self.HasPrefix(new_word):
if DEBUG:
print 'No words found starting with "%s"' %(new_word)
return solutions
# This is a valid, complete words.
if self.IsWord(new_word):
new_solution = FoundWord(new_word, previous_locations)
if DEBUG:
print 'Found new solution: %s' %(str(new_solution))
solutions.append(new_solution)
# Recursively search all adjacent tiles
for new_loc in location.Adjacent():
if board.IsValidLocation(new_loc) and new_loc not in previous_locations:
# make a copy of the previous locations list so our current list
# is not affected by this recursive call.
defensive_copy = list(previous_locations)
solutions.extend(self.DoSolve(board, defensive_copy, new_loc, new_word))
else:
if DEBUG:
print 'Ignoring %s as it is invalid or already used.' %(str(new_loc))
return solutions
class UnsortedListBoardSolver(BoardSolver):
def __init__(self, valid_words):
self.valid_words = valid_words
def HasPrefix(self, prefix):
for word in self.valid_words:
if word.startswith(prefix):
return True
return False
def IsWord(self, word):
return word in self.valid_words
class SortedListBoardSolver(BoardSolver):
def __init__(self, valid_words):
self.valid_words = sorted(valid_words)
# http://docs.python.org/library/bisect.html#searching-sorted-lists
def index(self, a, x):
'Locate the leftmost value exactly equal to x'
i = bisect.bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
raise ValueError
def find_ge(self, a, x):
'Find leftmost item greater than or equal to x'
i = bisect.bisect_left(a, x)
if i != len(a):
return a[i]
raise ValueError
def HasPrefix(self, prefix):
try:
word = self.find_ge(self.valid_words, prefix)
return word.startswith(prefix)
except ValueError:
return False
def IsWord(self, word):
try:
self.index(self.valid_words, word)
except ValueError:
return False
return True
class TrieBoardSolver(BoardSolver):
def __init__(self, valid_words):
self.trie = trie.Trie()
for index, word in enumerate(valid_words):
# 0 evaluates to False which screws up trie lookups; ensure value is 'truthy'.
self.trie.add(word, index+1)
def HasPrefix(self, prefix):
curr_node, remainder = self.trie._find_prefix_match(prefix)
return not remainder
# Extremely slow method - does a lot of extra work creating the
# list of results, only to throw it away.
#return len(self.trie.find_prefix_matches(prefix)) > 0
def IsWord(self, word):
return word in self.trie
def ReadDictionary(path):
"""Returns a set of words found in the file indicated by 'path'."""
words = set([])
f = open(path, "r")
for line in f:
words.add(line.lower().strip())
f.close()
return words
def main():
words = ReadDictionary(sys.argv[1])
print 'Read %d words' %(len(words))
trie_solver = TrieBoardSolver(words)
list_solver = UnsortedListBoardSolver(words)
sorted_list_solver = SortedListBoardSolver(words)
if TIMING_TEST:
iters = [1, 10, 100]
solvers = [trie_solver, sorted_list_solver] #, list_solver, sorted_list_solver]
for num_iters in iters:
random_boards = [Board(4,4) for x in range(num_iters)]
for solver in solvers:
start = datetime.datetime.now()
for board in random_boards:
solver.Solve(board)
end = datetime.datetime.now()
elapsed = end - start
seconds = elapsed.seconds + (elapsed.microseconds / 1E6)
avg_time = seconds / num_iters
print 'Took %.3f seconds to solve %d boards; avg %.3f with %s' %(seconds,
num_iters, avg_time, solver)
b = Board(4, 4)
b.board = [
['l', 'qu', 'r', 'e'],
['s', 'l', 'u', 's'],
['a', 't', 'i', 'c'],
['n', 'r', 'e', 'n']
]
print 'Solving with binary search'
sorted_solutions = sorted_list_solver.Solve(b)
print 'Solving with trie'
trie_solutions = trie_solver.Solve(b)
# Results should be exactly the same
assert sorted_solutions == trie_solutions
for solution in sorted(sorted_solutions):
print solution
words = sorted(set([s.word for s in sorted_solutions]))
print '\n'.join(words)
if __name__ == '__main__':
main()
# From https://bitbucket.org/woadwarrior/trie/src/6bc187d770ba/python/trie.py
# ndunn patched the find_full_match method to handle prefix strings correctly,
# as well as adding comments.
_SENTINEL = ()
class Trie(object) :
__slots__ = ['root']
def __init__( self ) :
self.root = [None,{}]
def __getstate__( self ) :
if any(self.root) :
return self.root
else :
return False
def __setstate__(self, s) :
self.root = s
def __contains__( self, s ) :
if self.find_full_match(s,_SENTINEL) is _SENTINEL :
return False
return True
def add( self, key, value ) :
# Traverse through the nodes
curr_node = self.root
for ch in key :
node = curr_node[1]
if ch in node :
curr_node = node[ch]
else :
curr_node = node[ch] = [None,{}]
curr_node[0] = value
def _find_prefix_match( self, key ) :
curr_node = self.root
remainder = key
for ch in key :
if ch in curr_node[1] :
curr_node = curr_node[1][ch]
else :
break
remainder = remainder[1:]
return [curr_node,remainder]
def find_full_match( self, key, fallback=None ) :
'''
Returns the value associated with the key if found else, returns fallback
'''
curr_node, remainder = self._find_prefix_match(key)
stored_value = curr_node[0]
has_stored_value = stored_value is not None
if not remainder and has_stored_value:
return stored_value
return fallback
def find_prefix_matches( self, prefix ) :
l = self._find_prefix_match( prefix )
# If there's a remainder, then there's nothing in the tree that matches
if l[1] :
return []
# stack starts ith the current node
stack = [l[0]]
ret = []
while stack :
d = stack.pop()
if d[0] :
ret.insert(0,d[0])
for c in d[1] :
stack.append(d[1][c])
return ret
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.