Challenging dynamic programming problem

Question

This is a toned down version of a computer vision problem I need to solve. Suppose you are given parameters n,q and have to count the number of ways of assigning integers 0..(q-1) to elements of n-by-n grid so that for each assignment the following are all true

1. No two neighbors (horizontally or vertically) get the same value.
2. Value at positions (i,j) is 0
3. Value at position (k,l) is 0

Since (i,j,k,l) are not given, the output should be an array of evaluations above, one for every valid setting of (i,j,k,l)

A brute force approach is below. The goal is to get an efficient algorithm that works for q<=100 and for n<=18.

def tuples(n,q):   return [[a,]+b for a in range(q) for b in tuples(n-1,q)] if n>1 else [[a] for a in range(q)]  def isvalid(t,n):   grid=[t[n*i:n*(i+1)] for i in range(n)];   for r in range(n):     for c in range(n):       v=grid[r][c]       left=grid[r][c-1] if c>0 else -1       right=grid[r][c-1] if c<n-1 else -1       top=grid[r-1][c] if r > 0 else -1       bottom=grid[r+1][c] if r < n-1 else -1       if v==left or v==right or v==top or v==bottom:         return False   return True  def count(n,q):   result=[]   for pos1 in range(n**2):     for pos2 in range(n**2):       total=0       for t in tuples(n**2,q):         if t[pos1]==0 and t[pos2]==0 and isvalid(t,n):           total+=1        result.append(total)    return result  assert count(2,2)==[1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1] 

Update 11/11 I've also asked this on TopCoder forums, and their solution is the most efficient one I've seen so far (about 3 hours for n=10, any q, from author's estimate)

Answer 1

Maybe this sounds too simple, but it works. Randomly distribute values to all the cells until only two are empty. Test for adjacency of all values. Compute the average the percent of successful casts vs. all casts until the variance drops to within an acceptable margin.

The risk goes to zero and the that which is at risk is only a little runtime.

Answer 2

This isn't an answer, just a contribution to the discussion which is too long for a comment.

tl; dr; Any algorithm which boils down to, "Compute the possibilities and count them," such as Eric Lippert's or a brute force approach won't work for @Yaroslav's goal of q <= 100 and n <= 18.

Let's first think about a single n x 1 column. How many valid numberings of this one column exist? For the first cell we can pick between q numbers. Since we can't repeat vertically, we can pick between q - 1 numbers for the second cell, and therefore q - 1 numbers for the third cell, and so on. For q == 100 and n == 18 that means there are q * (q - 1) ^ (n - 1) = 100 * 99 ^ 17 valid colorings which is very roughly 10 ^ 36.

Now consider any two valid columns (call them the bread columns) separated by a buffer column (call it the mustard column). Here is a trivial algorithm to find a valid set of values for the mustard column when q >= 4. Start at the top cell of the mustard column. We only have to worry about the adjacent cells of the bread columns which have at most 2 unique values. Pick any third number for the mustard column. Consider the second cell of the mustard column. We must consider the previous mustard cell and the 2 adjacent bread cells with a total of at most 3 unique values. Pick the 4th value. Continue to fill out the mustard column.

We have at most 2 columns containing a hard coded cell of 0. Using mustard columns, we can therefore make at least 6 bread columns, each with about 10 ^ 36 solutions for a total of at least 10 ^ 216 valid solutions, give or take an order of magnitude for rounding errors.

There are, according to Wikipedia, about 10 ^ 80 atoms in the universe.

Therefore, be cleverer.