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 

不是。

[请注意，这不是因为它扔掉大部分信息一般问题的一个很好的解决方案，但是，它是直截了当]