Nonogram Solver

You're given a grid with r rows and c columns. For each row and each column you get a clue, which is a list of integers describing the run lengths of consecutive filled cells on that line, in order. A clue like [3, 1] means "a block of three filled cells, at least one empty cell, then a block of one filled cell." The special clue [0] means the line is entirely empty.

Here's a 5x5 whose solution spells out a heart. The left panel is what you receive, showing empty cells with the clues on each axis, while the right panel shows the solved grid.

Row clues run along the left of each grid, column clues along the top. Every filled run in the solution matches its clue from left to right for rows and top to bottom for columns. If no valid filling exists, the solver returns null.

The test suite runs four sizes, starting at 5x5, then 10x10, then 15x15, and finishing with a single 25x25. Each timed test has its own budget, and the wrinkle is that an approach that passes 10x10 can blow the budget on 15x15 by orders of magnitude.

The most direct way to attack this is backtracking. Walk the cells left-to-right across each row, top row first, then the next row, and so on. At each cell, try FILLED, recurse into the next cell, and if that sub-search fails, try EMPTY instead. When the recursion reaches the bottom-right corner, check whether every row's and every column's runs agree with their clues. If yes, you're done. If no, unwind.