Python的nonogram獨特

Question

我想寫一個Python腳本，以確定是否給定的nonogram是獨一無二的。我目前的劇本跑得太長，所以我想知道是否有人有任何想法。

據我瞭解，一般nonogram問題是NP難問題。然而，我知道兩條關於我的給定非圖形的信息：

1. 當分別將黑/白框分別表示爲0和1時，我知道每個圖像有多少個。
2. 我只考慮6x6 nonograms。

我最初使用蠻力的方法（所以2 ^36案件）。然而，知道了（1），我能夠將其縮小到n選k（36個選擇數爲零）的情況。但是，當k接近18時，這仍然是〜2^33個案例。需要幾天運行。

任何想法，我怎麼可能會加速這個嗎？它甚至有可能嗎？

同樣，我不關心解決辦法是什麼 - 我已經擁有它。我試圖確定的是，如果解決方案是獨一無二的。

編輯： 這是不完全的完整代碼，但有總體思路：

def unique(nonogram): 
    found = 0 
    # create all combinations with the same number of 1s and 0s as incoming nonogram 
    for entry in itertools.combinations(range(len(nonogram)), nonogram.count(1)): 
     blank = [0]*len(nonogram) # initialize blank nonogram 
     for element in entry: 
      blank[element] = 1 # distribute 1s across nonogram 
     rows = find_rows(blank) # create row headers (like '2 1') 
     cols = find_cols(blank) 
     if rows == nonogram_rows and cols == nonogram_cols: 
      found += 1 # row and col headers same as original nonogram 
     if found > 1: 
      break  # obviously not unique 
    if found == 1: 
     print('Unique nonogram') 

Answer 1

我想不出一個聰明的方式來證明唯一性，其他比解決問題，但6x6的是足夠小，我們可以基本上做一個蠻力的解決方案。爲了加快速度，我們可以遍歷所有滿意的行，而不是循環遍歷每一個可能的非圖。像這樣的（注：未經測試）的東西應該工作：

from itertools import product, groupby 
from collections import defaultdict 

def vec_to_spec(v): 
    return tuple(len(list(g)) for k,g in groupby(v) if k) 

def build_specs(n=6): 
    specs = defaultdict(list) 
    for v in product([0,1], repeat=n): 
     specs[vec_to_spec(v)].append(v) 
    return specs 

def check(rowvecs, row_counts, col_counts): 
    colvecs = zip(*rowvecs) 
    row_pass = all(vec_to_spec(r) == tuple(rc) for r,rc in zip(rowvecs, row_counts)) 
    col_pass = all(vec_to_spec(r) == tuple(rc) for r,rc in zip(colvecs, col_counts)) 
    return row_pass and col_pass 

def nonosolve(row_counts, col_counts): 
    specs = build_specs(len(row_counts)) 
    possible_rows = [specs[tuple(r)] for r in row_counts] 
    sols = [] 
    for poss in product(*possible_rows): 
     if check(poss, row_counts, col_counts): 
      sols.append(poss) 
    return sols 

從中我們得知，

>>> rows = [[2,2],[4], [1,1,1,], [2], [1,1,1,], [3,1]] 
>>> cols = [[1,1,2],[1,1],[1,1],[4,],[2,1,],[3,2]] 
>>> nonosolve(rows, cols) 
[((1, 1, 0, 0, 1, 1), (0, 0, 1, 1, 1, 1), (1, 0, 0, 1, 0, 1), 
(0, 0, 0, 1, 1, 0), (1, 0, 0, 1, 0, 1), (1, 1, 1, 0, 0, 1))] 
>>> len(_) 
1 

是獨一無二的，但

>>> rows = [[1,1,1],[1,1,1], [1,1,1,], [1,1,1], [1,1,1], [1,1,1]] 
>>> cols = rows 
>>> nonosolve(rows, cols) 
[((0, 1, 0, 1, 0, 1), (1, 0, 1, 0, 1, 0), (0, 1, 0, 1, 0, 1), (1, 0, 1, 0, 1, 0), (0, 1, 0, 1, 0, 1), (1, 0, 1, 0, 1, 0)), 
((1, 0, 1, 0, 1, 0), (0, 1, 0, 1, 0, 1), (1, 0, 1, 0, 1, 0), (0, 1, 0, 1, 0, 1), (1, 0, 1, 0, 1, 0), (0, 1, 0, 1, 0, 1))] 
>>> len(_) 
2 

不是。

[請注意，這不是因爲它扔掉大部分信息一般問題的一個很好的解決方案，但是，它是直截了當]