Sunday, March 30, 2014

Nonogram puzzle solver in 2D (part 2/2).

Nonogram puzzle solver in 2D

My previous post got us up to solving constraints in a one dimensional nonogram vector.
You really need to have read the previous post recently as this follows on from that.
In [9]:
from __future__ import print_function, division
from pprint import pprint as pp
from copy import deepcopy
try: from itertools import izip_longest as zip_longest
except ImportError: from itertools import zip_longest
from nonovector import newforces, nonovector

# All the recap I will do for now:
help(nonovector)
help(newforces)
Help on function nonovector in module nonovector:

nonovector(blocks, cells, force0, force1)
    Generate all block positions for a nonogram row.
    
    Arguments:
        blocks:         list of block widths starting from lhs.
        cells:          Size of row.
        force0:         Cell indices that must be clear.
        force1:         Cell indices that must be filled.
    
    Generates:
        [ (bpos, blength), ...]
        
        Where:
            bpos is the minimum index to a span of connected blocks.
            blength is the number of consecutive blocks spanned.

Help on function newforces in module nonovector:

newforces(vecgen, cells)
    Extracts what cells are always zero/one in all vectors from generator vecgen
    
    Returns lists: (always0, always1)


Role reversal

I very early found out that I needed to be able to generate nonograms from pictures so I had something to solve so wrote pic2gram that can extract the clue information from an array of ones and zeroes
So with my training 2D example picture of
01110
11010
01110
00110
00111
I can generate a puzzle.
In [10]:
def line2blocks(line='01110011110011101111001111011100'):
    'Extract nonogram block clues from a line of 0/1 characters'
    blocks, runlength = [], 0
    for i, ch in enumerate(line):
        if ch == '1':
            runlength += 1
        elif runlength:         # ch != '1' so at end of block
            blocks.append(runlength)
            runlength = 0
    if runlength:               # block ends at RH border
        blocks.append(runlength)
    elif not blocks:            # Corner case: empty line depicted as one zero-length block
        blocks.append(0)
    return blocks                            

def pic2gram(pic):
    "convert rectangular '01' pic to nonogram clue"
    array = pic.strip().split('\n')
    vert  = [line2blocks(line) for line in array]
    horiz = [line2blocks(line) for line in zip(*array)] # Remember zip(*x) to transpose
    return (vert, horiz)
In [11]:
smallex = '''\
01110
11010
01110
00110
00111'''

verticalclues, horizontalclues = pic2gram(smallex)
print('verticalclues = %r\nhorizontalclues = %r' % (verticalclues, horizontalclues))
verticalclues = [[3], [2, 1], [3], [2], [3]]
horizontalclues = [[1], [3], [1, 3], [5], [1]]

Hmmm. Still need prettier output:
In [12]:
def parray(array, zro='_', one='#'):
    'prettyprint 0/1 array'
    for row in array:
        print('|' + '|'.join(one if cell in (1, '1') else zro
                             for cell in row) + '|')
    print('')

print('ORIGINAL PICTURE\n')
parray(smallex.split('\n'))
ORIGINAL PICTURE

|_|#|#|#|_|
|#|#|_|#|_|
|_|#|#|#|_|
|_|_|#|#|_|
|_|_|#|#|#|


That is better, now adding the generated clues to the printout:
In [13]:
def parrayclues(array, clues, zro='_', one='#'):
    'prettyprint 0/1 array with associated clues'
    vert, horiz = clues
    for row, v in zip(array, vert):
        print('|' + 
              '|'.join(one if cell in (1, '1') else zro for cell in row) + 
              '| # ' +
              ' '.join(str(i) for i in v))
    hstr = [' #' + ' '.join(str(b) for b in col) for col in horiz]
    verttext = [' '.join(ch) for ch in zip_longest(*hstr, fillvalue=' ')]
    for line in verttext:
        print(' ' + line)
In [14]:
vert, horiz = puzzle = pic2gram(pic=smallex)
array = smallex.split('\n')
print('ORIGINAL PICTURE WITH GENERATED NONOGRAM CLUES\n')
parrayclues(array, puzzle, one='X')
ORIGINAL PICTURE WITH GENERATED NONOGRAM CLUES

|_|X|X|X|_| # 3
|X|X|_|X|_| # 2 1
|_|X|X|X|_| # 3
|_|_|X|X|_| # 2
|_|_|X|X|X| # 3
          
 # # # # #
 1 3 1 5 1
          
     3    

The clues for columns are printed vertically downwards beneath the columns.

Solution Strategy

I can use newforces on each row to find the forced positions of each cell on the row and store them in two bit-arrays an array of bits denoting which cells must be zero and another bit-array for those that must be one. Bits in these bit arrays are 1 to force a value at that position. The value forced is blank for the forcing zero array or filled for the forcing 1 array.
newforces will load initial forces from the bit-arrays and store its updates back to them for each row of the grid.
If we spin the data 90 degrees, i.e. transpose things, we can run newforces on all the columns in a similar manner gradually refining the bit-array of forces until the bit-arrays reach a steady state.

Forces bit arrays

OK fix0grid and fix1grid aren't actually bits but they could be. I just don't need the space saving
In [15]:
# BLank initial forces bit-arrays
rowlen, collen = len(vert), len(horiz)
fix0grid = [[0] * collen for i in range(rowlen)] # Inner lists are distinct! 
fix1grid = [[0] * collen for i in range(rowlen)]
pp(fix0grid)
[[0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0]]

Pretty-printer for forced-cell info

We could do with another pretty-printer. This one formats with errors marked with err i.e. if some cell is forced to both a zero and a 1; and que (Fawlty towers ref.), if the cell currently is not forced to either state.
In [16]:
def pforces(f0grid, f1grid, clues, zro='_', one='#', err='!', que='?'):
    '''
    prettyprint to string from force0/1 arrays with associated clues
    
    Returns (string, , )
    
    '''
    vert, horiz = clues
    out = []
    for row0, row1, v in zip(f0grid, f1grid, vert):
        out.append(
              '|' + 
              '|'.join(one if cell1 and not cell0 
                         else (zro if cell0 and not cell1 else (
                                err if cell0 and cell1 else que)) 
                       for cell0, cell1 in zip(row0, row1)) + 
              '| # ' +
              ' '.join(str(i) for i in v))
    hstr = [' #' + ' '.join(str(b) for b in col) for col in horiz]
    verttext = [' '.join(ch) for ch in zip_longest(*hstr, fillvalue=' ')]
    for line in verttext:
        out.append(' ' + line)
    text = '\n'.join(out)
    return (text, text.count(err), text.count(que))
Lets try it:
In [17]:
# BLank initial forces bit-arrays
rowlen, collen = len(vert), len(horiz)
fix0grid = [[0] * collen for i in range(rowlen)] # Inner lists are distinct! 
fix1grid = [[0] * collen for i in range(rowlen)]

txt, err, que = pforces(fix0grid, fix1grid, puzzle)
print('Starting state of %i errors and %i unknown cells:\n' % (err, que))   
print(txt)
Starting state of 0 errors and 25 unknown cells:

|?|?|?|?|?| # 3
|?|?|?|?|?| # 2 1
|?|?|?|?|?| # 3
|?|?|?|?|?| # 2
|?|?|?|?|?| # 3
          
 # # # # #
 1 3 1 5 1
          
     3    

Update rows of fixed cell values

In [18]:
def newfixes(blocklist, fix0grid, fix1grid):
    '''
    In-line update to rows of fix0grid, fix1grid, based on current values.
    blocklist is the list of clues for all rows. 
    '''
    for row, (blocks, f0, f1) in enumerate(zip(blocklist, fix0grid, fix1grid)):
        # Extract forces for this row
        force0 = [i for i, cell in enumerate(f0) if cell]
        force1 = [i for i, cell in enumerate(f1) if cell]
        # Update forces for this row
        force0, force1 = newforces(nonovector(blocks, len(f0), force0, force1), len(f0))
        # Apply changes back to bit-arrays
        for col in force0:
            fix0grid[row][col] = 1
        for col in force1:
            fix1grid[row][col] = 1
    # remember, no return value as it works by updating fix0grid and fix1grid in-place.
No independent test of newfixes except for its use in the main loop

Main loop for nonogram solver

First I apply newfixes to vertical clues and rows of the bit-arrays to find fixes. Next, in the same iteration, I transpose the arrays and use the horizontal clues on what will then be the columns of the bit-arrays of forces.
I keep enough past state to detect when improvements stop.
In [19]:
iterations = 0
oldf0 = oldf1 = []      # Guaranteed to fail initial values
while (oldf0 != fix0grid or oldf1 != fix1grid) and (que or err):
    oldf0, oldf1 = deepcopy(fix0grid), deepcopy(fix1grid)   # Take a copy of current state.
    iterations += 1
    newfixes(vert, fix0grid, fix1grid)
    # transpose and do other direction
    fix0grid, fix1grid = list(list(z) for z in zip(*fix0grid)), list(list(z) for z in zip(*fix1grid))
    newfixes(horiz, fix0grid, fix1grid)
    # transpose back
    fix0grid, fix1grid = list(list(z) for z in zip(*fix0grid)), list(list(z) for z in zip(*fix1grid))
    txt, err, que = pforces(fix0grid, fix1grid, puzzle)
    print('\nIteration %i has %i errors and %i unknown cells\n' % (iterations, err, que))   
    print(txt)

print('\nFinished!')
Iteration 1 has 0 errors and 12 unknown cells

|?|?|#|#|?| # 3
|?|#|_|#|?| # 2 1
|?|#|#|#|?| # 3
|?|?|#|#|?| # 2
|?|_|#|#|?| # 3
          
 # # # # #
 1 3 1 5 1
          
     3    

Iteration 2 has 0 errors and 1 unknown cells

|_|#|#|#|?| # 3
|#|#|_|#|_| # 2 1
|_|#|#|#|_| # 3
|_|_|#|#|_| # 2
|_|_|#|#|#| # 3
          
 # # # # #
 1 3 1 5 1
          
     3    

Iteration 3 has 0 errors and 0 unknown cells

|_|#|#|#|_| # 3
|#|#|_|#|_| # 2 1
|_|#|#|#|_| # 3
|_|_|#|#|_| # 2
|_|_|#|#|#| # 3
          
 # # # # #
 1 3 1 5 1
          
     3    

Finished!

Remember that the original nonogram was:
In [20]:
parrayclues(array, puzzle, one='X')
|_|X|X|X|_| # 3
|X|X|_|X|_| # 2 1
|_|X|X|X|_| # 3
|_|_|X|X|_| # 2
|_|_|X|X|X| # 3
          
 # # # # #
 1 3 1 5 1
          
     3    

Looks OK to me!

Finished?

Sometimes the clues are not sufficient to generate a unique picture. I suspect that in those cases the above algorithm would only be a partial solution. It would need to be followed by iterating through all the possibilities of block positions in two dimensions covering the remaining unknown cells and returning the first iteration of block positions that fits the ending set of fix0grid and fix1grid values.

END.

Nonogram puzzle solver (part 1).

Nonogram puzzle solver

What is a Nonogram?

Think of a monochrome picture made up of filled or unfilled cells on a rectangular grid.
|_|X|X|X|_|
|X|X|_|X|_|
|_|X|X|X|_|
|_|_|X|X|_|
|_|_|X|X|X|
Add to every horizontal line as a comment, the size of all horizontal connected runs of set blocks (sometimes calle ones and zeroes as well as set/unset cells).
A line of
|X|X|_|X|_|
has two runs of connected blocks. The first of length 2, the second of length 1 - The order is important.
This means that the above line is annotated as
|X|X|_|X|_| # 2 1
If you generate the annotations for all the rows you end up with:
|_|X|X|X|_| # 3
|X|X|_|X|_| # 2 1
|_|X|X|X|_| # 3
|_|_|X|X|_| # 2
|_|_|X|X|X| # 3
You can do the same for each of the columns in turn; annotating them with sthe size of each block in the column counted from top to bottom. I add the annotations at the bottom this time to produce:
|_|X|X|X|_| # 3
|X|X|_|X|_| # 2 1
|_|X|X|X|_| # 3
|_|_|X|X|_| # 2
|_|_|X|X|X| # 3
 # # # # #
 1 3 1 5 1

     3    
The above states, for example, that the middle column has a block of length 1 above a block of length 3 where the annotation of '#1 3' is written vertically downwards under the column.
To turn this into the puzzle, only the empty grid and the annotations (which become clues), are given.
|_|_|_|_|_| # 3
|_|_|_|_|_| # 2 1
|_|_|_|_|_| # 3
|_|_|_|_|_| # 2
|_|_|_|_|_| # 3
 # # # # #
 1 3 1 5 1

     3    
The job is then to fill the grid with blocks in such a way that the clues are all satisfied. (Sometimes the puzzle can be solved but generate a different picture).

Solving it yourself

Now is the time to read this part of the wikipedia entry on nonograms and try and understand the techniques used when solving nonograms by hand.

Computer Solution

I learned of nonograms as the first part of trying to solve them by computer. When reading about how to solve it by hand, I was also thinking of how to program a solver in Python.
I thought of a three1 step process:
  1. Given a clue and how many cells are in a row, generate all the permutations of block positions that can satisfy the clue.
  2. Generate all the permutations of block positions that can satisfy the clues as above, but also knowing what cells of the row are predetermined to be either set or unset.
  3. Given all the possible block position permutations for a row, generate lists of what cells are always unset, and what are always set.
  4. The above being most of an algorithm to in effect solve a one dimensional nonovector; hook it up to solve the two dimensional case.
Voxels anyone ;-)

Block permutations

To tell the truth I had to extract this code from what I wrote as I went straight for a partial solution to the second step. but I digress.
In [3]:
from __future__ import print_function
from pprint import pprint as pp

def nonoblocks(blocks, cells):
    '''
    Generate all block positions for a nonogram row.

    Arguments:
        blocks:         list of block lengths starting from lhs.
        cells:          Size of row.

    Generates:
        [ (bpos, blength), ...]
        
        Where:
            bpos is the minimum index to a span of connected blocks.
            blength is the number of consecutive blocks spanned.
    '''
    assert sum(blocks) + len(blocks)-1 <= cells, \
        'Those blocks will not fit in those cells'
    blength, brest = blocks[0], blocks[1:]      # Deal with the first block of length
    minspace4rest = sum(1+b for b in brest)     # The other blocks need space
    # Slide the start position from left to max RH index allowing for other blocks.
    for bpos in range(0, cells - minspace4rest - blength + 1):
        if not brest:
            # No other blocks to the right so just yield this one.
            yield [(bpos, blength)]
        else:
            # More blocks to the right so create a *sub-problem* of placing
            # the brest blocks in the cells one space to the right of the RHS of 
            # this block.
            offset = bpos + blength +1
            nonoargs = (brest, cells - offset)  # Pre-compute arguments to nonoargs
            # recursive call to nonoblocks yields multiple sub-positions
            for subpos in nonoblocks(*nonoargs):
                # Remove the offset from sub block positions
                rest = [(offset + bp, bl) for bp, bl in subpos]
                # Yield this block plus sub blocks positions
                vec = [(bpos, blength)] + rest
                yield vec
In [4]:
# Lets try the case: |_|_|_|_|_| # 2 1
for positions in nonoblocks(blocks=[2, 1], cells=5):
    print(positions)
    
[(0, 2), (3, 1)]
[(0, 2), (4, 1)]
[(1, 2), (4, 1)]

Not bad but we need a better way to view these blocks so...

Block viewer

In [5]:
def pblocks(vec, cells):
    'Prettyprints each run of blocks with a different letter'
    vector = ['.'] * cells
    for ch, (bp, bl) in enumerate(vec, ord('A')):
        for i in range(bp, bp + bl):
            vector[i] = chr(ch)
    return ''.join(vector)
In [6]:
# Lets try the case again: |_|_|_|_|_| # 2 1
cells = 5
for positions in nonoblocks(blocks=[2, 1], cells=cells):
    print(pblocks(positions, cells))
AA.B.
AA..B
.AA.B

OK. There's a bit of recursion in nonoblocks() to get your head around.
  • Consider the first block and the rest of the other blocks.
  • The rest has a minimum space they can be squashed into.
  • The first block can be in any position from the LHS up to the minimum space needed for blocks to the right of it.
  • In effect I slide the LH block from the left generating allof its positions.
  • I recursively append the positions of all the rest of the blocks in the space to the right of the left most block, (taking care to leave a space).
(Much debug effort elided).

Vector permutations: Block permutations with forced set/unset cells

A change of syntax. Lets also call a row of cells a vector.
We now have restrictions on cell contents. Maybe some cells have been predetermined to be zero, or predetermined to be one. I handle this by generating all block positions as in nonoblock() but I skip any which would violate the predetermined 'forces'.
In [7]:
def nonovector(blocks, cells, force0, force1):
    '''
    Generate all block positions for a nonogram row.

    Arguments:
        blocks:         list of block widths starting from lhs.
        cells:          Size of row.
        force0:         Cell indices that must be clear.
        force1:         Cell indices that must be filled.

    Generates:
        [ (bpos, blength), ...]
        
        Where:
            bpos is the minimum index to a span of connected blocks.
            blength is the number of consecutive blocks spanned.
    '''
    assert sum(blocks) + len(blocks)-1 <= cells, \
        'Those blocks will not fit in those cells'
    blength, brest = blocks[0], blocks[1:]
    minspace4rest = sum(1+b for b in brest)
    for bpos in range(0, cells - minspace4rest - blength + 1):
        ## Fisrt set of force checks limit recursion
        if any(bpos <= f0 < (bpos + blength) for f0 in force0):
            continue # forced space is inside block
        if any((f1 < bpos or f1 == (bpos + blength)) for f1 in force1):
            continue # forced fill is separate on LHS, or extends, block
        if not brest:
            yield [(bpos, blength)]
        else:
            offset = bpos + blength +1
            nonoargs = (brest,
                               cells - offset,
                               # The predetermined forces are offset too
                               [(f0 - offset) for f0 in force0 if f0 >= offset],
                               [(f1 - offset) for f1 in force1 if f1 >= offset]
                              )
            for subpos in nonovector(*nonoargs):
                rest = [(offset + bp, bl) for bp, bl in subpos]
                vec = [(bpos, blength)] + rest
                ## Second final set of force checks.                
                expand = vexpand(vec, cells)
                if (any(expand[f0] != '.' for f0 in force0) or
                    any(expand[f1] == '.' for f1 in force1)):
                        continue # forced value not preserved
                yield vec
In [8]:
def vexpand(blocks, cells):
    "Expands the blocks to a string of either '.' or '#' (Or '?' for overlaps)"
    vector = ['.'] * cells
    for bp, bl in blocks:
        for i in range(bp, bp + bl):
            vector[i] = '#' if vector[i] == '.' else '?'
    return ''.join(vector)

def pvector(vec, cells, force0, force1):
    '''
    Prettyprints each run of blocks with a different uppercase letter 
    showing force1's as the lowercase letter and force0's as '_' instead of
    '.' for a space.
    Problems show as '!'
    '''
    vector = ['.'] * cells
    for i in force0:
        vector[i] = '_'
    for i in force1:
        vector[i] = '1' if vector[i] == '.' else '!'
    for ch, (bp, bl) in enumerate(vec, ord('A')):
        for i in range(bp, bp + bl):
            vector[i] = chr(ch) if vector[i] == '.' else (
                        '!' if vector[i] == '_' else chr(ch).lower())
    return ''.join(vector)
In [9]:
# Lets try the case: |_|_|_|_|_| # 2 1
# but this time we have predetermined that there is a 1 and zero in the following positions:
# |_|1|0|_|_| # 2 1
blocks, cells, force0, force1 = [2, 1], 5, [2], [1]
for positions in nonovector(blocks, cells, force0, force1):
    print(pvector(positions, cells, force0, force1))
Aa_B.
Aa_.B

Generating lists of what cells are always unset/set

From the previous examples output we can see that the first and second cells are always one and the third cell is always zero. We need to be able to extract that information so ...
In [10]:
def newforces(vecgen, cells):
    '''
    Extracts what cells are always zero/one in all vectors from generator vecgen

    Returns lists: (always0, always1)
    '''    
    expanded = [vexpand(vec, cells) for vec in vecgen]  # generate all expanded perms
    # We have successive permutations as rows.
    # We compare each column to see if they are all zero or all one
    # This needs transposing rows to columns
    transposed = list(zip(*expanded))
    force0, force1 = [], []
    for i, tr in enumerate(transposed):
        tr0 = tr[0]
        if all(t == tr0 for t in tr[1:]):
            if tr0 == '.':
                force0.append(i)
            else:
                force1.append(i)
    return force0, force1
In [11]:
# That same case again of: |_|1|0|_|_| # 2 1
blocks, cells, force0, force1 = [2, 1], 5, [2], [1]

for positions in nonovector(blocks, cells, force0, force1):
    print(pvector(positions, cells, force0, force1))
vecgen = nonovector(blocks, cells, force0, force1)
print('\nNew fixed: force0, force1 =', newforces(vecgen, cells))
print('(Indexed from zero not one, Python style.)')
Aa_B.
Aa_.B

New fixed: force0, force1 = ([2], [0, 1])
(Indexed from zero not one, Python style.)

Yay! I think that is it. We can try the vector examples from the wikipedia article:

Wikipedia vector examples

In [12]:
def _pv(vec, cells, force0, force1):
    'massaged prettyprinter'
    txt = list(pvector(vec, cells, force0, force1))
    return '|' + '|'.join(txt) + '|'

if __name__ == '__main__':
#if 1:
    for blocks, cells, force0, force1, comment in (
            ([8], 10, [], [], 'Simple boxes'),
            ([4, 3], 10, [], [], 'Simple boxes'),
            #([3, 1], 10, [], [], 'Simple ??'),
            ([3, 1], 10, [], [3, 8], 'Simple spaces'),
            ([3, 2], 10, [4, 6], [], 'Forcing'),
            ([5], 10, [], [2], 'Glue'),
            ([1, 3], 10, [2], [0, 4], 'Glue'),
            ([5, 2, 2], 15, [], [2, 3, 5, 6, 10, 12], 'Joining and splitting')):
        print('\n%r\n  Blocks:  %r\n  Initial fixes:\n    %s' % (comment, blocks, _pv([], cells, force0, force1)))        
        #print('  blocks, cells, force0, force1 =', (blocks, cells, force0, force1))
        print('  All possibilities:')
        for vector in nonovector(blocks, cells, force0, force1):
            print('   ', _pv(vector, cells, force0, force1))
        newforce0, newforce1 =  newforces(nonovector(blocks, cells, force0, force1), cells)
        print('  Resultant fixes:')
        print('   ', _pv([], cells, newforce0, newforce1))
'Simple boxes'
  Blocks:  [8]
  Initial fixes:
    |.|.|.|.|.|.|.|.|.|.|
  All possibilities:
    |A|A|A|A|A|A|A|A|.|.|
    |.|A|A|A|A|A|A|A|A|.|
    |.|.|A|A|A|A|A|A|A|A|
  Resultant fixes:
    |.|.|1|1|1|1|1|1|.|.|

'Simple boxes'
  Blocks:  [4, 3]
  Initial fixes:
    |.|.|.|.|.|.|.|.|.|.|
  All possibilities:
    |A|A|A|A|.|B|B|B|.|.|
    |A|A|A|A|.|.|B|B|B|.|
    |A|A|A|A|.|.|.|B|B|B|
    |.|A|A|A|A|.|B|B|B|.|
    |.|A|A|A|A|.|.|B|B|B|
    |.|.|A|A|A|A|.|B|B|B|
  Resultant fixes:
    |.|.|1|1|.|.|.|1|.|.|

'Simple spaces'
  Blocks:  [3, 1]
  Initial fixes:
    |.|.|.|1|.|.|.|.|1|.|
  All possibilities:
    |.|A|A|a|.|.|.|.|b|.|
    |.|.|A|a|A|.|.|.|b|.|
    |.|.|.|a|A|A|.|.|b|.|
  Resultant fixes:
    |_|.|.|1|.|.|_|_|1|_|

'Forcing'
  Blocks:  [3, 2]
  Initial fixes:
    |.|.|.|.|_|.|_|.|.|.|
  All possibilities:
    |A|A|A|.|_|.|_|B|B|.|
    |A|A|A|.|_|.|_|.|B|B|
    |.|A|A|A|_|.|_|B|B|.|
    |.|A|A|A|_|.|_|.|B|B|
  Resultant fixes:
    |.|1|1|.|_|_|_|.|1|.|

'Glue'
  Blocks:  [5]
  Initial fixes:
    |.|.|1|.|.|.|.|.|.|.|
  All possibilities:
    |A|A|a|A|A|.|.|.|.|.|
    |.|A|a|A|A|A|.|.|.|.|
    |.|.|a|A|A|A|A|.|.|.|
  Resultant fixes:
    |.|.|1|1|1|.|.|_|_|_|

'Glue'
  Blocks:  [1, 3]
  Initial fixes:
    |1|.|_|.|1|.|.|.|.|.|
  All possibilities:
    |a|.|_|B|b|B|.|.|.|.|
    |a|.|_|.|b|B|B|.|.|.|
  Resultant fixes:
    |1|_|_|.|1|1|.|_|_|_|

'Joining and splitting'
  Blocks:  [5, 2, 2]
  Initial fixes:
    |.|.|1|1|.|1|1|.|.|.|1|.|1|.|.|
  All possibilities:
    |.|.|a|a|A|a|a|.|.|B|b|.|c|C|.|
  Resultant fixes:
    |_|_|1|1|1|1|1|_|_|1|1|_|1|1|_|

Nonograms in one dimension completed

The above code is saved as nonovector.py and imported in the next installment that expands things to two dimensions.

Notes/References

  • 1: I am aware that the list may not have the stated number of elements.