これは、私が解決しなければならないコンピューター ビジョンの問題のトーンダウン バージョンです。パラメーター n,q が与えられ、n 行 n 列のグリッドの要素に整数 0..(q-1) を割り当てる方法の数を数えなければならない場合を想定して、割り当てごとに以下がすべて真になるようにします。
- 2 つの隣接 (水平または垂直) が同じ値になることはありません。
- 位置 (i,j) の値は 0
- 位置 (k,l) の値は 0
(i,j,k,l) が指定されていないため、出力は (i,j,k,l) の有効な設定ごとに 1 つずつ、上記の評価の配列になります。
ブルート フォース アプローチを以下に示します。目標は、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 時間)