Time complexity of Boggle solver

Question

Here is a (ugly) algorithm for finding all words in Boggle:

d = {'cat', 'dog', 'bird'}

grid = [
    ['a', 'd', 'c', 'd'],
    ['o', 'c', 'a', 't'],
    ['a', 'g', 'c', 'd'],
    ['a', 'b', 'c', 'd']
]

found = {}

N = 4

def solve(row, col, prefix):
    if prefix in d and prefix not in found:
        found[prefix] = True
        print prefix

    for i in xrange(max(0, row - 1), min(N, row + 2)):
        for j in xrange(max(0, col - 1), min(N, col + 2)):
            c = grid[i][j]
            if c != '#' and not (row == i and col == j):
                grid[i][j] = '#'
                solve(i, j, prefix + c)
                grid[i][j] = c


for row in xrange(N):
    for col in xrange(N):
        c = grid[row][col]
        grid[row][col] = '#'
        solve(row, col, c)
        grid[row][col] = c

What is the Big-O runtime of this algorithm? I believe it is O((N²)!), but I'm not sure.

Answer 1

The solve function turns one element after an other into #, in worst case until the whole grid contains only #. But since you start at a specific point in the grid and only allow the next # to be a direct neighbor, you do not get all the (N²)! possible permutations. You only get something like O(8N2), because every node in your grid has at most 8 direct neighbors. Elements at the borders have less neighbors, so you can improve this a little bit.

The for-loop at the end, iterates over all elements in the grid and calls the solve function, so it would be O(N2⋅8N2) in total.

Notice: 8N2 is much better than (N²)! as long as N² ≥ 20, i.e. N ≥ 5.

Notice: I assumed, that d has only a constant length. If this is not true, you have to add the length of d to the complexity calculations.