Python nonogram uniqueness

Question

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

Answer 1

I can't think of a clever way to prove uniqueness other than to solve the problem, but 6x6 is small enough that we can basically do a brute-force solution. To speed things up, instead of looping over every possible nonogram we can loop over all satisfying rows. Something like this (note: untested) should work:

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

from which we learn that

>>> 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

is unique, but

>>> 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

isn't.

[Note that this isn't a very good solution for the problem in general as it throws away most of the information, but it was straightforward.]