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:
- Given a clue and how many cells are in a row, generate all the permutations of block positions that can satisfy the clue.
- 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.
- Given all the possible block position permutations for a row, generate lists of what cells are always unset, and what are always set.
- 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)
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))
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))
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.)')
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))
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.
This comment has been removed by a blog administrator.
ReplyDelete