## Wednesday, February 15, 2012

### solving boggle puzzle in the newspaper

Starting with a puzzle like this:
N  N  O  L  H
O  E  H  Y  O
D  I  P  M  C
R  A  M  O  P
E  P  S  H  A

The idea is you make unique words length 3 or greater using each letter at most once and moving through the grid either up, down, left, right, or diagonally from letter to letter to spell out the word.
I wrote a computer program that searched through a dictionary and found every possible word. It found 741. Here is a list of all the words of 7 or more letters it found:
AMIDOLS
COMPARE
DAMPENS
EIDOLON
ENHALOS
HEIRDOM
HYPHENS
MAIDENS
MIDRASH
NONPAID
OOMPAHS
PARAPHS
PARDONS
PERCOID
PHENOLS
POPEDOM
PRIMPED
RAMPION
RAPHIDE
SAPHENA
SARCOID
DAMPENER
DIAPHONE
DRAMSHOP
EIDOLONS
LYCOPENE
LYMPHOMA
RAMPIONS
SAMPHIRE
SAPHENAE
HOMOPHONE
LYMPHOMAS

My source code in Python:

import copy
class words():
f = []

print(word)
self.f.append(word)
def shut(self):
r = open("result.txt", "w")
self.d = set(self.f)
for word in self.d:
r.write(word+'\n')
r.write(str(len(self.f)) + '\n')
r.close()
result = words()

def check(word, puzzle, pos, n):
p = puzzle
p[pos[0]][pos[1]][1] = False
if n+1 == len(word):
if len(word) > 2:
return True
try:
if (p[pos[0]][pos[1]-1][0] == word[n+1]) and p[pos[0]][pos[1]-1][1] == True:
check(word, copy.deepcopy(p), [pos[0], pos[1]-1], n+1)
except:
pass
try:
if (p[pos[0]-1][pos[1]][0] == word[n+1]) and p[pos[0]-1][pos[1]][1] == True:
check(word, copy.deepcopy(p), [pos[0]-1, pos[1]], n+1)
except:
pass
try:
if (p[pos[0]-1][pos[1]-1][0] == word[n+1]) and p[pos[0]-1][pos[1]-1][1] == True:
check(word, copy.deepcopy(p), [pos[0]-1, pos[1]-1], n+1)
except:
pass
try:
if (p[pos[0]][pos[1]+1][0] == word[n+1]) and p[pos[0]][pos[1]+1][1] == True:
check(word, copy.deepcopy(p), [pos[0], pos[1]+1], n+1)
except:
pass
try:
if (p[pos[0]+1][pos[1]][0] == word[n+1]) and p[pos[0]+1][pos[1]][1] == True:
check(word, copy.deepcopy(p), [pos[0]+1, pos[1]], n+1)
except:
pass
try:
if (p[pos[0]+1][pos[1]+1][0] == word[n+1]) and p[pos[0]+1][pos[1]+1][1] == True:
check(word, copy.deepcopy(p), [pos[0]+1, pos[1]+1], n+1)
except:
pass
try:
if (p[pos[0]+1][pos[1]-1][0] == word[n+1]) and p[pos[0]+1][pos[1]-1][1] == True:
check(word, copy.deepcopy(p), [pos[0]+1, pos[1]-1], n+1)
except:
pass
try:
if (p[pos[0]-1][pos[1]+1][0] == word[n+1]) and p[pos[0]-1][pos[1]+1][1] == True:
check(word, copy.deepcopy(p), [pos[0]-1, pos[1]+1], n+1)
except:
pass

def main():
puzzle = [[['N', True], ['N', True], ['O', True], ['L', True], ['H', True]], [['O', True], ['E', True], ['H', True], ['Y', True], ['O', True]], [['D', True], ['I', True], ['P', True], ['M', True], ['C', True]], [['R', True], ['A', True], ['M', True], ['O', True], ['P', True]], [['E', True], ['P', True], ['S', True], ['H', True], ['A', True]]]