Sudoku is a discrete constraints satisfaction problem which is modeled as an underdetermined linear
system. This report focuses on applying some new signal processing approaches to solve sudoku and
comparisons to some of the existing approaches are implemented. As our goal is not meant for
sudoku only in the long term, we applied approximate solvers using optimization theory methods. A
Semi Definite Relaxation (SDR) convex optimization approach was developed for solving sudoku. The
idea of Iterative Adaptive Algorithm for Amplitude and Phase Estimation (IAA-APES) from array
processing is also being used for sudoku to utilize the sparsity of the sudoku solution as is the case in
sensing applications. LIKES and SPICE were also tested on sudoku and their results are compared with
l1-norm minimization, weighted l1-norm, and sinkhorn balancing. SPICE and l1-norm are equivalent
in terms of accuracy, while SPICE is slower than l1-norm. LIKES and weighted l1-norm are equivalent
and better than SPICE and l1-norm in accuracy. SDR proved to be best when the sudoku solutions are
unique; however the computational complexity is worst for SDR. The accuracy for IAA-APES is
somewhere between SPICE and LIKES and its computation speed is faster than both.