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”
You must be logged in to post a comment.