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.
from__future__importprint_function,divisionfrompprintimportpprintasppfromcopyimportdeepcopytry:fromitertoolsimportizip_longestaszip_longestexceptImportError:fromitertoolsimportzip_longestfromnonovectorimportnewforces,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.
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.
[ (bpos, blength), ...]
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:
Extracts what cells are always zero/one in all vectors from generator vecgen
Returns lists: (always0, always1)
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.
defline2blocks(line='01110011110011101111001111011100'):'Extract nonogram block clues from a line of 0/1 characters'blocks,runlength=,0fori,chinenumerate(line):ifch=='1':runlength+=1elifrunlength:# ch != '1' so at end of blockblocks.append(runlength)runlength=0ifrunlength:# block ends at RH borderblocks.append(runlength)elifnotblocks:# Corner case: empty line depicted as one zero-length blockblocks.append(0)returnblocksdefpic2gram(pic):"convert rectangular '01' pic to nonogram clue"array=pic.strip().split('\n')vert=[line2blocks(line)forlineinarray]horiz=[line2blocks(line)forlineinzip(*array)]# Remember zip(*x) to transposereturn(vert,horiz)
The clues for columns are printed vertically downwards beneath the columns.
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
# BLank initial forces bit-arraysrowlen,collen=len(vert),len(horiz)fix0grid=[*collenforiinrange(rowlen)]# Inner lists are distinct! fix1grid=[*collenforiinrange(rowlen)]pp(fix0grid)
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.
defpforces(f0grid,f1grid,clues,zro='_',one='#',err='!',que='?'):''' prettyprint to string from force0/1 arrays with associated clues Returns (string, , ) '''vert,horiz=cluesout=forrow0,row1,vinzip(f0grid,f1grid,vert):out.append('|'+'|'.join(oneifcell1andnotcell0else(zroifcell0andnotcell1else(errifcell0andcell1elseque))forcell0,cell1inzip(row0,row1))+'| # '+' '.join(str(i)foriinv))hstr=[' #'+' '.join(str(b)forbincol)forcolinhoriz]verttext=[' '.join(ch)forchinzip_longest(*hstr,fillvalue=' ')]forlineinverttext:out.append(' '+line)text='\n'.join(out)return(text,text.count(err),text.count(que))
Lets try it:
# BLank initial forces bit-arraysrowlen,collen=len(vert),len(horiz)fix0grid=[*collenforiinrange(rowlen)]# Inner lists are distinct! fix1grid=[*collenforiinrange(rowlen)]txt,err,que=pforces(fix0grid,fix1grid,puzzle)print('Starting state of %i errors and %i unknown cells:\n'%(err,que))print(txt)
defnewfixes(blocklist,fix0grid,fix1grid):''' In-line update to rows of fix0grid, fix1grid, based on current values. blocklist is the list of clues for all rows. '''forrow,(blocks,f0,f1)inenumerate(zip(blocklist,fix0grid,fix1grid)):# Extract forces for this rowforce0=[ifori,cellinenumerate(f0)ifcell]force1=[ifori,cellinenumerate(f1)ifcell]# Update forces for this rowforce0,force1=newforces(nonovector(blocks,len(f0),force0,force1),len(f0))# Apply changes back to bit-arraysforcolinforce0:fix0grid[row][col]=1forcolinforce1: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.
iterations=0oldf0=oldf1=# Guaranteed to fail initial valueswhile(oldf0!=fix0gridoroldf1!=fix1grid)and(queorerr):oldf0,oldf1=deepcopy(fix0grid),deepcopy(fix1grid)# Take a copy of current state.iterations+=1newfixes(vert,fix0grid,fix1grid)# transpose and do other directionfix0grid,fix1grid=list(list(z)forzinzip(*fix0grid)),list(list(z)forzinzip(*fix1grid))newfixes(horiz,fix0grid,fix1grid)# transpose backfix0grid,fix1grid=list(list(z)forzinzip(*fix0grid)),list(list(z)forzinzip(*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!')
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.