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)
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
I can generate a puzzle.
0111011010011100011000111I 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))
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'))
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')
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)
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)
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 loopMain 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!')
Remember that the original nonogram was:
In [20]:
parrayclues(array, puzzle, one='X')
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.
