January 7, 2024
We’ve been working on The Nonogram Project. Just what is a Nonogram? It’s a matrix puzzle with a truly unique beginning. There was a design competition in Tokyo in 1987 to design a picture created on the side of a skyscraper by turning the lights in the windows on and off. The competition was won by Non Ishida. Her name is where Nonogram came from.
This isn’t just a player, it’s a solver and eventually an editor as well.
The numbers at the top and left of the matrix are the clues.
The 4 at the top left tells us that there is a single block of 4 in column 0. (we’re coders, we always start counting at zero!).
The 2 2 at the left, tells us that there are 2 blocks of 2 in row 2.
The way we coded the solver has two levels - The board solver and the row and column solvers. The Board Solver runs all the row and column solvers and then merges their results. Let’s watch them work!
Rows 0 & 2 are solved when loaded.
When the clues are loaded, the blocks are packed as tightly as possible on the left.
Rows 1, 3 & 4 are all the same and produce no solved cells
Column 2, with no clues is solved when loaded.
Columns 0 & 5 produce 3 solved cells.
Columns 1 & 3 produce no solved cells
After all of the row and column solvers are done stepping, this is what we have.
If a cell is solved by either a row or column solver, it’s marked as solved. If there are conflicts, the board can’t be solved by this algorithm and is likely unsolvable without guessing.
The solvers re-load from the clues, respecting the cells marked as solved.
The board solver, when he does the merge, sees that the board is solved.