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.

Answer 3

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 41 hours hours for n=10, any q, from author's estimate)

I'm the author. Not 41, just 3 embarrassingly parallelizable CPU hours. I've counted symmetries. For n=10 there are only 675 really distinct pairs of (i,j) and (k,l). My program needs ~ 16 seconds per each.

Answer 4

I'm building a contribution based on the contribution to the discussion by Dave Aaron Smith.

Let's not consider for now the last two constraints ((i,j) and (k,l)).

With only one column (nx1) the solution is q * (q - 1) ^ (n - 1).

---

(q-1)q-1q-2

Same thing for (3,2) : q-1 or q-2 solutions.

We can see we have a binary tree of possibilities and we need to sum over that tree. Let's assume left child is always "same color on top and at left" and right child is "different colors".

By computing over the tree the number of possibilities for the left column to create a such configurations and the number of possibilities for the new cells we are coloring we would count the number of possibilities for coloring two columns.

But let's now consider the probability distribution foe the coloring of the second column : if we want to iterate the process, we need to have an uniform distribution on the second column, it would be like the first one never existed and among all coloring of the first two column we could say things like 1/q of them have color 0 in the top cell of second column.

Without an uniform distribution it would be impossible.

The problem : is the distribution uniform ?

Answer : We would have obtain the same number of solution by building first the second column them the first one and then the third one. The distribution of the second column is uniform in that case so it also is in the first case.

We can now apply the same "tree idea" to count the number of possibilities for the third column.

I will try to develop on that and build a general formula (since the tree is of size 2^n we don't want to explicitly explore it).

Answer 5

A few observations which might help other answerers as well:

1. The values 1..q are interchangeable - they could be letters and the result would be the same.
2. The constraints that no neighbours match is a very mild one, so a brute force approach will be excessively expensive. Even if you knew the values in all but one cell, there would still be at least q-8 possibilities for q>8.
3. The output of this will be pretty long - every set of i,j,k,l will need a line. The number of combinations is something like n²(n²-3), since the two fixed zeroes can be anywhere except adjacent to each other, unless they need not obey the first rule. For n=100 and q=18, the maximally hard case, this is ~ 100⁴ = 100 million. So that's your minimum complexity, and is unavoidable as the problem is currently stated.
4. There are simple cases - when q=2, there are the two possible checkerboards, so for any given pair of zeroes the answer is 1.

Point 3 makes the whole program O( n²(n²-3) ) as a minimum, and also suggests that you will need something reasonably efficient for each pair of zeroes as simply writing 100 million lines without any computation will take a while. For reference, at a second per line, that is 1x10⁸s ~ 3 years, or 3 months on a 12-core box.

I suspect that there is an elegant answer given a pair of zeroes, but I'm not sure that there is an analytic solution to it. Given that you can do it with 2 or 3 colours depending on the positions of the zeroes, you could split the map into a series of regions, each of which uses only 2 or 3 colours, and then it's just the number of different combinations of 2 or 3 in q (qC2 or qC3) for each region times the number of regions, times the number of ways of splitting the map.

Answer 6

I'm not a mathematician, but it occurs to me that there ought to be an analytical solution to this problem, namely:

First, compute now many different colourings are possible for NxN board with Q colours (including that neighbours, defined as having common edge don't get same color). This ought to be pretty simple formula.

Then figure out how many of these solutions have 0 in (i,j), this should be 1/Q's fraction.

Then figure out how many of remaining solutions have 0 in (k,l) depending on manhattan distance |i-k|+|j-l|, and possibly distance to the board edge and "parity" of these distances, as in distance divisible by 2, divisible by 3, divisible by Q.

The last part is the hardest, though I think it might still be doable if you are really good at math.