Nonogram Solver

For a few years now, I’ve been playing a mobile game called Nonogram.com. It’s on the Play store and the App store, and probably other places as well. It’s a pretty simple game so I thought it might be fun to make something that can solve it. I’m used to working on vague, fuzzy problems so it was a bit of a shock to me when the first thing I tried actually worked.

The game

A Nonogram is a game where the player fills in a grid of squares based on a set of hints. Already, you can see similarities with Sudoku and KenKen and other games in that grid-filling genre. A hint in a nonogram tells the player how to group the filled-in squares in a row or column. The Wikipedia page I linked has a deeper explanation of nonograms and an overview of common approaches to solving them if you’re interested. It also links to some examples of nonogram solvers. I didn’t actually look at any other implementations because I just wanted to make a quick little project. Maybe I’ll consult those if I decide to improve my solver.

High hopes

I began this project intending to create an n-dimensional version of the original game. I did make a version like that, but things started getting a little out of hand so I decided to stick to a simple 2D square game at first and then add other features later. That decision turned out to be a good one since my code’s performance turned out to be, shall we say, lacking.

Depth-first search with backtracking

My code solves a nonogram one row at a time. It starts at the top and searches through all of the legal rows until it finds a solution. It does a depth-first search and then backtracks to the last legal state whenever it finds a contradiction in its solution. It does this pretty slowly and inefficiently because I didn’t really expect it to work. To make matters worse, Python itself is not exactly blazing fast.

I based my approach on a few Sudoku solvers I found on the internet. It seems to be a fairly common project—there are so many that I couldn’t find the exact ones I used when I went back and searched for links to them. Instead of searching through all of the numbers that can go in a Sudoku square (1-9), I search through all of the legal rows that satisfy the hint for a given row. It’s pretty easy to generate these legal rows, so maybe the best approach would be to generate legal columns as well and find some way to combine the two to prune the search a bit.

In the end, 4 x 4 is the largest board that my code can solve consistently. It sometimes gets lucky on a 5 x 5.

Optimization

I tried a few things to speed up the solver. The largest improvement came when I cached the results of a function that I called constantly. Overall, the solver went from evaluating about 20k positions per second to about 80k positions per second according to cProfile and snakeviz.

Appendix A: Multiple Solutions

One of the assumptions I had before this project was that a set of hints corresponds to exactly one solution. I hadn’t ever thought too much about that assumption, but it turns out to be very wrong. Below are some examples of boards with multiple solutions that I came across.

3 x 3 example

Solution 1

Solution 2

5 x 5 example

Solution 1

Solution 2

This was also the first 5 x 5 my code happened to solve. I’ve decided it doesn’t count because there are only nine possible arrangements of the legal rows in this puzzle. Not exactly a convincing demonstration of the search algorithm’s prowess.