3

I'm trying to write a Python script to determine if a given nonogram is unique. My current script just takes way too long to run so I was wondering if anyone had any ideas.

I understand that the general nonogram problem is NP-hard. However, I know two pieces of information about my given nonograms:

  1. When representing the black/white boxes as 0s and 1s, respectively, I know how many of each I have.
  2. I'm only considering 6x6 nonograms.

I initially used a brute force approach (so 2^36 cases). Knowing (1), however, I was able to narrow it down to n-choose-k (36-choose-number of zeroes) cases. However, when k is near 18, this is still ~2^33 cases. Takes days to run.

Any ideas how I might speed this up? Is it even possible?

Again, I don't care what the solution is -- I already have it. What I'm trying to determine is if that solution is unique.

EDIT: This isn't exactly the full code but has the general idea:

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')
4

1 回答 1

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

不是。

[请注意，这对于一般问题来说并不是一个很好的解决方案，因为它会丢弃大部分信息，但它很简单。]

于 2013-07-16T05:21:11.743 回答