PicSol - a .net Nonogram/Picross Solver Library
Nonograms - also known as Griddlers, Picture Crosswords, or Picross - are pretty cool puzzles, kind of like a more visual Crossword puzzle or Sudoku. Of all the games on my New 2DS XL, Mario's Picross and the Picross e series are near the top of my Activity Log (beaten only by Smash Bros).
I got curious about algorithmic solutions to those Nonograms, which seems deceptively easy, but is actually NP-complete. When trying to solve a Nonogram, often I can to only fill in one or a few cells of a group, which then leads to another cell that can be filled in (or X-ed out), and step by step, cell by cell, I solve the Nonogram. Now, that assumes that the Nonogram is properly designed - if that's the case, then there is always at least one cell that either must definitely be filled or definitely be empty.
All of Jupiter's games are well designed - even the most tricky ones (with a bunch of 1's and 2's and no big numbers) always follow the mantra of There's always at least one cell that has a definitive solution. There are a lot of other games on the market (Steam returns about 15 games when searching for Picross or Nonogram), and some are not well designed and actually require guessing.
I ended up (after a bunch of googling approaches and other existing solvers) with a solution that's mostly brute force - generate all possibilities for a row and column, then eliminate those that can't be correct, rinse and repeat until there's only 1 possibility left for each row and column, or until we determined that the Nonogram is actually unsolvable. There are some shortcuts that we can take, e.g, when a row/column is empty, completely filled, or completely filled with gaps in-between them.
I've created PicSol, a library for .net Standard 2.0 and .net Framework 4.0 (or newer) and available on Nuget which offers a Solver for Nonograms.
Check out the README for information on how to use it, or look at the Console project in the GitHub repository.
- My Software