CareerCup

#!/usr/bin/env python

import sys
import pprint

def combinationsStartingAt(matrix, start, maxLength, combs):
    inRange = lambda point: point[0] in range(len(matrix)) and point[1] in range(len(matrix))

    (i, j) = start
    words = set()
    for dr, dc in ( (0, -1), (-1, -1), (1, -1), (0, 1), (-1, 1), (1, 1), (-1, 0), (1, 0)):
        next = (i + dr, j + dc)
        if inRange(next):
            earlierCombs = combs[maxLength - 1][next]
            #print '----- earlier:', maxLength - 1, ' on next:', next, ' is', earlierCombs
            #print '====', filter(lambda x: len(x) < 2 or x[1] != (i, j), earlierCombs)
            tempWords = set(((i, j),) + tempWord for tempWord in filter(lambda x: len(x) < 2 or x[1] != (i, j), earlierCombs))
            words = words.union(tempWords)

    return words
    

def combinationsOf(matrix, maxLength, combs):
    words = set()
    #print 'max:', maxLength
    for i in range(len(matrix)):
        for j in range(len(matrix)):
            start = (i, j)
            if maxLength == 1:
                combs[1][(i, j)] = set([((i, j),)])
            else:
                words = combinationsStartingAt(matrix, (i, j), maxLength, combs)
                combs[maxLength][(i, j)] = words

    return words

def toWords(matrix, combs):
    def toWord(x):
        return ''.join(matrix[i][j] for i, j in x)

    result = {}
    for key in combs.keys():
        result[key] = set()
        for index, poss in combs[key].iteritems():
            for word in poss:
                result[key].add(toWord(word))
    return result

def combinations(matrix):
    maxLength = 5
    combs = {}
    for length in range(1, maxLength + 1):
        combs[length] = {}
        combinationsOf(matrix, length, combs)
    combs = toWords(matrix, combs)
    pprint.pprint(combs[maxLength])

matrix = [
    [ 'A', 'B', 'C', 'D' ],
    [ 'E', 'K', 'L', 'A' ],
    [ 'C', 'A', 'M', 'N' ],
    [ 'D', 'I', 'N', 'G' ]
]
combinations(matrix)

Use backtracking to store all possible words that can be formed in trie and then answer each query of presence of words in O(world length)