Nonograms

def row_count(row_clue, length):
    "For a given clue, returns the the number of possibilities."
    cc = row_clue[0]  # cc is current clue
    if len(row_clue) == 1:
        if cc == 0:
            return 1
        return length - cc + 1
    tail = row_clue[1:]
    min_tail = sum(tail) + len(tail) - 1
    return sum(row_count(tail, length-(cc+i+1)) for i in xrange(length-cc-min_tail))

def all_rle(row_clue, length):
    "Yields all possible RLEs for a row_clue."
    cc = row_clue[0]  # cc is current clue
    if len(row_clue) == 1:
        if cc == 0:
            yield '0' * length
            raise StopIteration
        for i in xrange(length-cc+1):
            yield '0'*i + '1'*cc + '0'*(length-cc-i)
        raise StopIteration
    tail = row_clue[1:]
    min_tail = sum(tail) + len(tail) - 1
    for i in xrange(length - cc - min_tail):
        cs = '0'*i + '1'*cc + '0'  # current string
        gap = cc + i + 1
        for ts in all_rle(tail, length - gap):  # tail strings
            yield cs + ts