Python 非图唯一性

Question

我正在尝试编写一个 Python 脚本来确定给定的非图是否唯一。我当前的脚本运行时间太长，所以我想知道是否有人有任何想法。

我知道一般的非图问题是 NP 难的。但是，我知道关于我给定的非图的两条信息:

1. 当分别将黑/白框表示为 0 和 1 时，我知道我有多少个。
2. 我只考虑 6x6 非图。

我最初使用的是蛮力方法(所以 2^36 个案例)。然而，知道 (1) 后，我能够将其缩小到 n-choose-k(36-choose-number of zeroes)情况。然而，当 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

不是。

[请注意，这不是解决一般问题的好方法，因为它丢弃了大部分信息，但它很简单。]