Last time, we considered the linear equations and linear inequalities that the solution of a nonogram must satisfy. Let us now solve the minimization problem and see how well compressive sensing works. I will consider several examples, then offer a simple fix for the problems that we will encounter.

Continue reading “Solving Nonograms with Compressive Sensing: Part 4”

We know how to represent the solution of a nonogram as a sparse vector . Let us now design the constraints; they will be linear equations and linear inequalities that the entries of must satisfy according to the nonogram. The only information that the nonogram provides are the row and column sequences, so we want to make the most of it. Afterwards, we obtain the sparse vector by minimizing its 1-norm under these constraints. I will discuss the code and the results in the next and final post.

Continue reading “Solving Nonograms with Compressive Sensing: Part 3”

3. Introducing compressive sensing

Today, we will consider how to turn the solution of a nonogram into a sparse vector. But first, let me take a detour and illustrate an approach that Oscar and I initially had considered and comment on its strengths and weaknesses in solving the puzzle.

Throughout our discussion, we will consider the stylish lambda example:

Continue reading “Solving Nonograms with Compressive Sensing: Part 2”

Over the next month, I want to present a project that my friend Oscar and I came up with and worked on for a class. We developed a new technique to solve nonograms using compressive sensing.

The trick is knowing how to write the solution to any nonogram as a sparse vector . Sparse means there are many entries that are zero, and compressive sensing considers this fact to find a unique solution to an underdetermined system! It’s strikingly different from traditional linear algebra, which says that an underdetermined system that has a solution has, in fact, infinitely many solutions.

Our method avoids (1) partial fill-ins, (2) heuristics, and (3) over-complication, and only requires that we solve a binary integer programming problem. There was one issue that Oscar and I couldn’t solve in time, however. I hope that I can now by revisiting this project after three years. Ideas are welcome!

Continue reading “Solving Nonograms with Compressive Sensing: Part 1”