grid = \
[['E', 'E', 'C', 'A'],
 ['A', 'L', 'E', 'P'],
 ['H', 'N', 'B', 'O'],
 ['Q', 'T', 'T', 'Y']]

def traverse_grid(x, y, s, i, used):
	if i >= len(s):
		return True
	result = False
	for (nx, ny) in filter(lambda coords: 0 <= coords[0] < 4 and 0 <= coords[1] < 4 and coords != (x, y) and grid[coords[0]][coords[1]] == s[i] and (coords[0] * 4 + coords[1]) not in used, reduce(lambda a, b: a + b, [[(x + m, y + n) for m in xrange(-1, 2)] for n in xrange(-1, 2)])):
		result = result or traverse_grid(nx, ny, s, i + 1, dict(used, **{nx * 4 + ny: True}))
		if result: break
	return result

seen = {}
count = 0
for word in open('words.txt', 'r'):
	word = word.strip().upper()
	if word in seen:
		continue
	seen[word] = True
	if filter(lambda x: traverse_grid(x / 4, x % 4, word, 0, {}), range(16)):
		count += 1
		print count, word

exit(0)

class Node:
	letter = ''
	count = 0
	nexts = {}

	def __init__(self, letter=''):
		self.letter = letter
root = Node()
def build_trie(prevnode, x, y, used):
	if grid[x][y] not in prevnode.nexts:
		prevnode.nexts[grid[x][y]] = Node(grid[x][y])
	currnode = prevnode.nexts[grid[x][y]]
	for (nx, ny) in filter(lambda coords: 0 <= coords[0] < 4 and 0 <= coords[1] < 4 and coords != (x, y) and (coords[0] * 4 + coords[1]) not in used, reduce(lambda a, b: a + b, [[(x + i, y + j) for i in xrange(-1, 2)] for j in xrange(-1, 2)])):
		build_trie(currnode, nx, ny, dict(used, **{nx * 4 + ny: True}))
for i in xrange(16):
	build_trie(root, i / 4, i % 4, {i * 4 + (i % 4): True})
	print i
def is_in_trie(currnode, s, i):
	while True:
		if s[i] not in currnode.nexts:
			return False
		currnode = currnode.nexts[s[i]]
		i += 1
	return True
count = 0
for word in open('words.txt', 'r'):
	word = word.strip().upper()
	if is_in_trie(root, word, 0):
		count += 1
		print count, word
exit(0)