Solving Sudoku by Sparse Signal Processing

University essay from KTH/Signalbehandling

Author: Muhammad Mohsin Abbasi; [2015]

Keywords: ;

Abstract:

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.

  AT THIS PAGE YOU CAN DOWNLOAD THE WHOLE ESSAY. (follow the link to the next page)