Spectacular Sudoku Solving with Super Sparse Signals
A fun an easy way to understand the concepts behind sparse signal processing. By using Sudoku puzzles as sparse signals, we are able to show the steps of sparse signal processing in a way that exemplifies its potential for a variety of fields.
Who are we?
We are Prava Dhulipalla and Allison Basore, students at Olin College of Engineering. Both of us are Electrical and Computer Engineering majors in the class Quantitative Engineering Analysis (QEA).
What is this project?
This is our final project for QEA. For this project we made an algorithm that solves Sudoku puzzles with sparse signal processing techniques and authored an “overnight” assignment that describes our process and the mathematical understanding behind our algorithm.
Who is this for?
This project is for students looking to learn and apply signal processing techniques. When making this project, we particularly focused on helping Quantitative Engineering Analysis students.
How does it work?
Please see the next few sections for more details on our mathematical analysis and its connection to signal processing.
What were the results?
Please see our results section for more information on the implementation and, of course, the results.
You might look at a sudoku puzzle, and then look at a signal (probably represented graphically in Matlab or some sort of Waveform-showing device - if you can see signals in the air you’re probably hallucinating), and think “these are two very different things”. In one way, you would be right. In another way, you would be wrong, and your mother would be disappointed in you.
What is sudoku? Yes, it is a puzzle. But it is also an underdetermined system of equations - when represented in a linear form, there are fewer equations than there are variables. The equation for sudoku, if you set up the matrices right, is:
b = Ax
Where x is the matrix that represents the solution, A is the logic matrix representing the logic formation, and b is a matrix of all 1s representing that all of the logic constraints have been met accordingly. However, for a 9 x 9 puzzle, the matrix A has more columns than rows - this means it is underdetermined.
Similarly, there a comparable equation in signal processing:
y = Ac
Where y is the original signal, A is the N-point Fourier Transform matrix, and c is the coefficient matrix. You will recognize this if you have ever done anything with the Fourier Transform - an algorithm that figures out those coefficients.
However, what if your signal is garbage? You have a few pixels missing from an image, or your mixtape was so fire you lost some of the samples. What do you do now? Well, you could realize that now, you have an underdetermined system of equations. And then you could rejoice, because you remember reading a website on a SUPER AWESOME SUDOKU SOLVER QEA II FINAL PROJECT that had the answers to your troubles!
One way to solve underdetermined systems of equations is through convex optimization? But what is convexity? And what is optimization? Well, I’ll tell you.
A convex set is a set of points that, given any two points within that set, the line segment joining of them also entirely lies within that set. A nonconvex function, thus, has the property that a line segment joining two points within that set can lie outside that set. The reason that this distinction is important is due to the fact that, as it turns out, a convex function is actually easier to solve. This is because it has one locally optimal minimum, whereas a nonconvex function has many locally optimal minima. It takes a lot of time to solve for these minima, let alone know whether any of them are feasible.
Luckily for us, both of our underdetermined systems of equations are convex. Accordingly, we can use convex optimization algorithms to help solve our problem.
Convex optimization helps us minimize convex functions over functions over convex sets. There are numerous convex optimization algorithms, however we’ll discuss only one here (for now).
In order to solve the sudoku puzzle, we used L1 norm minimizations, which minimizes the L1 norm constrained to the b = Ax equation:
minimize ||x||1 subject to b = Ax
The L1 norm is simply the summation of the absolute value of all of a vector’s components - and here we are minimizing it! If we add up all the absolute values of the function so that it equals a constant, you’ll find that it forms a diamond shape. The line that represents the solutions, then, will intersect with one of the corners of the diamond. Thus, if the constraints are well-set up and the problem is feasible, we can find a unique solution for an underdetermined system of equations.
Signal processing uses the same L1 norm minimization, often call basis pursuit:
minimize ||x||1 subject to y = Ac
The actual logistics behind the minimization are exactly the same, except the equation that it is subject to is a little different - the equation that pertains to signals. This especially helps when you want to recreate a signal at a higher frequency resolution than you actually have samples for. However, this begs the question - when would you need to do that? Making hardware that samples at a rate that meets the Nyquist sampling theorem is hard and costly, and so their tradeoff is using convex minimization techniques to “fill in the gaps,” and having less costly and area-consuming hardware.
Overall, the field of sparse signal processing, and especially compressive sensing (which deals with underdetermined systems of equations) has a lot of underlying mathematical concepts pertaining to many different problems/systems. Yes, sudoku is one of them, but there is also machine learning/deep learning, automatic control systems, finances and statistics, etc. And that is what this project is about - sometimes we get so wrapped up in a particular application that we can’t see it’s potential uses outside of that field. This project sure solved that for us - to the point where we feel burdened by our newfound knowledge. Just kidding . . . mostly.
Over the course of the project, we completed two algorithms for solving Sudoku problems, ran performance comparisons, write a problem set about our algorithms, made an adventure map of the project, and made a demonstration presentation.
Algorithm Results:
Our presentation slide deck that describes the other applications of our algorithm can be found here:
Slides
Our code for the algorithms can be found here:
Code
Our overnight that explains the math behind our algorithms can be found here:
Overnight