这是一个我需要解决的计算机视觉问题的简化版本。假设给定参数n和q，必须计算出将整数0..(q-1)分配给n×n网格元素的方法数，使得对于每个分配，以下情况均为真：
下面是一种暴力方法。目标是获得一种有效的算法，适用于q≤100，n≤18的情况。
- 相邻的两个元素（水平或垂直）没有相同的值。
- 位置(i,j)的值为0
- 位置(k,l)的值为0
下面是一种暴力方法。目标是获得一种有效的算法，适用于q≤100，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]
11/11更新 我也在TopCoder 论坛上提出了这个问题，他们的解决方案是目前为止最有效的（作者估计n=10时，任何q都只需要大约3小时）。
对于每个 i、j、k、l 的组合，位置 (i,j) 和 (k,l) 上的值都为 0。 - Loïc Février