Build a Nonographic Magnitude Optimizer™ A nonogram is a Japanese puzzle game in which the goal is to draw a black-and-white picture according to a list of contiguous regions, like so:



Define the nonographic magnitude of a row or column to be the number of contiguous black regions in that row or column. For example, the top row has a nonographic magnitude of 1, because there is one region of 2 squares in that row. The 8th row has a nonographic magnitude of 3 because it has 2, 2, 1.

An empty row or column has a nonographic magnitude of 0.



Your task is to write a program that takes a solution grid for a nonogram, and produces a solution grid with as few filled-in squares as possible where every row and column has the same nonographic magnutide as the given solution grid.

For example, a nonogram grid with all the squares filled in has a nonographic magnitude of 1 on every row or column:



The same nonographic magnitude could be achieved just by having a diagonal stripe through the grid, reducing the number of filled-in squares dramatically:





Your program will receive an input consisting of 50,000 lines from this file (1.32 MB tar.gz text file; 2.15 MB unzipped), each representing a single 16&times;16 nonogram solution grid with randomly (80% black) filled-in squares, and output another 50,000 lines, each containing the optimized solution grid for the corresponding input grid.

Each grid is represented as a base64 string with 43 characters (encoding squares from left to right, then top to bottom), and your program will need to return its output in the same format. For example, the first grid in the file is E/lu/+7/f/3rp//f799xn/9//2mv//nvj/bt/yc9/40=, and renders as:



The grid starts with E which maps to 000100, so the first six cells in the top row are all white except the fourth one. The next character is / which maps to 111111, so the next 6 cells are all black — and so on.



Your program must actually return a solution grid with the correct nonographic magnitudes for each of the 50,000 test cases. It is allowed to return the same grid as the input if nothing better was found.

The program to return the fewest total filled-in squares (in any language) is the winner, with shorter code being the tiebreaker.



Current scoreboard:


3,637,260 — Sleafar, Java
7,270,894 — flawr, Matlab
10,239,288 — Joe Z., Bash
Python 2 &amp; PuLP — 2,644,688 squares (optimally minimized); 10,753,553 squares (optimally maximized)

Minimally golfed to 1152 bytes



from pulp import*
x=0
f=open("c","r")
g=open("s","w")
for k,m in enumerate(f):
 if k%2:
    b=map(int,m.split())
    p=LpProblem("Nn",LpMinimize)
    q=map(str,range(18))
    ir=q[1:18]
    e=LpVariable.dicts("c",(q,q),0,1,LpInteger)
    rs=LpVariable.dicts("rs",(ir,ir),0,1,LpInteger)
    cs=LpVariable.dicts("cs",(ir,ir),0,1,LpInteger)
    p+=sum(e[r][c] for r in q for c in q),""
    for i in q:p+=e["0"][i]==0,"";p+=e[i]["0"]==0,"";p+=e["17"][i]==0,"";p+=e[i]["17"]==0,""
    for o in range(289):i=o/17+1;j=o%17+1;si=str(i);sj=str(j);l=e[si][str(j-1)];ls=rs[si][sj];p+=e[si][sj]&lt;=l+ls,"";p+=e[si][sj]&gt;=l-ls,"";p+=e[si][sj]&gt;=ls-l,"";p+=e[si][sj]&lt;=2-ls-l,"";l=e[str(i-1)][sj];ls=cs[si][sj];p+=e[si][sj]&lt;=l+ls,"";p+=e[si][sj]&gt;=l-ls,"";p+=e[si][sj]&gt;=ls-l,"";p+=e[si][sj]&lt;=2-ls-l,""
    for r,z in enumerate(a):p+=lpSum([rs[str(r+1)][c] for c in ir])==2*z,""
    for c,z in enumerate(b):p+=lpSum([cs[r][str(c+1)] for r in ir])==2*z,""
    p.solve()
    for r in ir:
     for c in ir:g.write(str(int(e[r][c].value()))+" ")
     g.write('\n')
    g.write('%d:%d\n\n'%(-~k/2,value(p.objective)))
    x+=value(p.objective)
 else:a=map(int,m.split())
print x


(NB: the heavily indented lines start with tabs, not spaces.)

Example output: https://drive.google.com/file/d/0B-0NVE9E8UJiX3IyQkJZVk82Vkk/view?usp=sharing

It turns out that problems like are readily convertible to Integer Linear Programs, and I needed a basic problem to learn how to use PuLP—a python interface for a variety of LP solvers—for a project of my own. It also turns out that PuLP is extremely easy to use, and the ungolfed LP builder worked perfectly the first time I tried it.

The two nice things about employing a branch-and-bound IP solver to do the hard work of solving this for me (other than not having to implement a branch and bound solver) are that


Purpose-built solvers are really fast. This program solves all 50000 problems in about 17 hours on my relatively low-end home PC. Each instance took from 1-1.5 seconds to solve.
They produce guaranteed optimal solutions (or tell you that they failed to do so). Thus, I can be confident that no one will beat my score in squares (although someone might tie it and beat me on the golfing part).


How to use this program

First, you'll need to install PuLP. pip install pulp should do the trick if you have pip installed.

Then, you'll need to put the following in a file called "c": https://drive.google.com/file/d/0B-0NVE9E8UJiNFdmYlk1aV9aYzQ/view?usp=sharing

Then, run this program in any late Python 2 build from the same directory. In less than a day, you'll have a file called "s" which contains 50,000 solved nonogram grids (in readable format), each with the total number of filled squares listed below it.

If you'd like to maximize the number of filled squares instead, change the LpMinimize on line 8 to LpMaximize instead. You will get output very much like this: https://drive.google.com/file/d/0B-0NVE9E8UJiYjJ2bzlvZ0RXcUU/view?usp=sharing

Input format

This program uses a modified input format, since Joe Z. said that we would be allowed to re-encode the input format if we like in a comment on the OP. Click the link above to see what it looks like. It consists of 10000 lines, each containing 16 numbers. The even numbered lines are the magnitudes for the rows of a given instance, while the odd numbered lines are the magnitudes for the columns of the same instance as the line above them. This file was generated by the following program:

from bitqueue import *

with open("nonograms_b64.txt","r") as f:
    with open("nonogram_clues.txt","w") as g:
        for line in f:
            q = BitQueue(line.decode('base64'))
            nonogram = []
            for i in range(256):
                if not i%16: row = []
                row.append(q.nextBit())
                if not -~i%16: nonogram.append(row)
            s=""
            for row in nonogram:
                blocks=0                         #magnitude counter
                for i in range(16):
                    if row[i]==1 and (i==0 or row[i-1]==0): blocks+=1
                s+=str(blocks)+" "
            print &gt;&gt;g, s
            nonogram = map(list, zip(*nonogram)) #transpose the array to make columns rows
            s=""
            for row in nonogram:
                blocks=0
                for i in range(16):
                    if row[i]==1 and (i==0 or row[i-1]==0): blocks+=1
                s+=str(blocks)+" "
            print &gt;&gt;g, s


(This re-encoding program also gave me an extra opportunity to test my custom BitQueue class I created for the same project mentioned above. It is simply a queue to which data can be pushed as sequences of bits OR bytes, and from which data can be popped either a bit or a byte at a time. In this instance, it worked perfectly.)

I re-encoded the input for the specific reason that to build an ILP, the extra information about the grids that were used to generate the magnitudes is perfectly useless. The magnitudes are the only constraints, and so the magnitudes are all I needed access to.

Ungolfed ILP builder

from pulp import *
total = 0
with open("nonogram_clues.txt","r") as f:
    with open("solutions.txt","w") as g:
        for k,line in enumerate(f):
            if k%2:
                colclues=map(int,line.split())
                prob = LpProblem("Nonogram",LpMinimize)
                seq = map(str,range(18))
                rows = seq
                cols = seq
                irows = seq[1:18]
                icols = seq[1:18]
                cells = LpVariable.dicts("cell",(rows,cols),0,1,LpInteger)
                rowseps = LpVariable.dicts("rowsep",(irows,icols),0,1,LpInteger)
                colseps = LpVariable.dicts("colsep",(irows,icols),0,1,LpInteger)
                prob += sum(cells[r][c] for r in rows for c in cols),""
                for i in rows:
                    prob += cells["0"][i] == 0,""
                    prob += cells[i]["0"] == 0,""
                    prob += cells["17"][i] == 0,""
                    prob += cells[i]["17"] == 0,""
                for i in range(1,18):
                    for j in range(1,18):
                        si = str(i); sj = str(j)
                        l = cells[si][str(j-1)]; ls = rowseps[si][sj]
                        prob += cells[si][sj] &lt;= l + ls,""
                        prob += cells[si][sj] &gt;= l - ls,""
                        prob += cells[si][sj] &gt;= ls - l,""
                        prob += cells[si][sj] &lt;= 2 - ls - l,""
                        l = cells[str(i-1)][sj]; ls = colseps[si][sj]
                        prob += cells[si][sj] &lt;= l + ls,""
                        prob += cells[si][sj] &gt;= l - ls,""
                        prob += cells[si][sj] &gt;= ls - l,""
                        prob += cells[si][sj] &lt;= 2 - ls - l,""
                for r,clue in enumerate(rowclues):
                    prob += lpSum([rowseps[str(r+1)][c] for c in icols]) == 2 * clue,""
                for c,clue in enumerate(colclues):
                    prob += lpSum([colseps[r][str(c+1)] for r in irows]) == 2 * clue,""
                prob.solve()
                print "Status for problem %d: "%(-~k/2),LpStatus[prob.status]
                for r in rows[1:18]:
                    for c in cols[1:18]:
                        g.write(str(int(cells[r][c].value()))+" ")
                    g.write('\n')
                g.write('Filled squares for %d: %d\n\n'%(-~k/2,value(prob.objective)))
                total += value(prob.objective)
            else:
                rowclues=map(int,line.split())
print "Total number of filled squares: %d"%total


This is the program that actually produced the "example output" linked above. Hence the extra long strings at the end of each grid, which I truncated when golfing it. (The golfed version should produce identical output, minus the words "Filled squares for ")

How it Works

cells = LpVariable.dicts("cell",(rows,cols),0,1,LpInteger)
rowseps = LpVariable.dicts("rowsep",(irows,icols),0,1,LpInteger)
colseps = LpVariable.dicts("colsep",(irows,icols),0,1,LpInteger)


I use an 18x18 grid, with the center 16x16 part being the actual puzzle solution. cells is this grid. The first line creates 324 binary variables: "cell_0_0", "cell_0_1", and so on. I also create grids of the "spaces" between and around the cells in the solution part of the grid. rowseps points to the 289 variables which symbolize the spaces that separate cells horizontally, while colseps similarly points to variables that mark the spaces that separate cells vertically. Here's a unicode diagram:

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|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|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
  - - - - - - - - - - - - - - - - 
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0


The 0s and □s are the binary values tracked by the cell variables, the |s are the binary values tracked by the rowsep variables, and the -s are the binary values tracked by the colsep variables.

prob += sum(cells[r][c] for r in rows for c in cols),""


This is the objective function. Just the sum of all the cell variables. Since these are binary variables, this is just exactly the number of filled squares in the solution.

for i in rows:
    prob += cells["0"][i] == 0,""
    prob += cells[i]["0"] == 0,""
    prob += cells["17"][i] == 0,""
    prob += cells[i]["17"] == 0,""


This just sets the cells around the outer edge of the grid to zero (which is why I represented them as zeroes above). This is the most expedient way to track how many "blocks" of cells are filled, since it ensures that every change from unfilled to filled (moving across a column or row) is matched by a corresponding change from filled to unfilled (and vice versa), even if the first or last cell in the row is filled. This is the sole reason for using an 18x18 grid in the first place. It's not the only way to count blocks, but I think it is the simplest.

for i in range(1,18):
    for j in range(1,18):
        si = str(i); sj = str(j)
        l = cells[si][str(j-1)]; ls = rowseps[si][sj]
        prob += cells[si][sj] &lt;= l + ls,""
        prob += cells[si][sj] &gt;= l - ls,""
        prob += cells[si][sj] &gt;= ls - l,""
        prob += cells[si][sj] &lt;= 2 - ls - l,""
        l = cells[str(i-1)][sj]; ls = colseps[si][sj]
        prob += cells[si][sj] &lt;= l + ls,""
        prob += cells[si][sj] &gt;= l - ls,""
        prob += cells[si][sj] &gt;= ls - l,""
        prob += cells[si][sj] &lt;= 2 - ls - l,""


This is the real meat of the logic of the ILP. Basically it requires that each cell (other than those in the first row and column) be the logical xor of the cell and separator directly to its left in its row and directly above it in its column. I got the constraints that simulate an xor within a {0,1} integer program from this wonderful answer: https://cs.stackexchange.com/a/12118/44289

To explain a bit more: this xor constraint makes it so that the separators can be 1 if and only if they lie between cells which are 0 and 1 (marking a change from unfilled to filled or vice versa). Thus, there will be exactly twice as many 1-valued separators in a row or column as the number of blocks in that row or column. In other words, the sum of the separators on a given row or column is exactly twice the magnitude of that row/column. Hence the following constraints:

for r,clue in enumerate(rowclues):
    prob += lpSum([rowseps[str(r+1)][c] for c in icols]) == 2 * clue,""
for c,clue in enumerate(colclues):
    prob += lpSum([colseps[r][str(c+1)] for r in irows]) == 2 * clue,""


And that's pretty much it. The rest just asks the default solver to solve the ILP, then formats the resulting solution as it writes it to the file.