AbstractsEngineering

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. ; Sudoku är ett diskret bivillkorsproblem som kan modelleras som ett underbestämt ekvationssystem. Denna rapport fokuserar på att tillämpa ett antal nya signalbehandlingsmetoder för att lösa sudoku och att jämföra resultaten med några existerande metoder. Eftersom målet inte enbart är att lösa sudoku, implementerades approximativa lösare baserade på optimeringsteori. En positiv-definit konvex relaxeringsmetod (SDR) för att lösa sudoku utvecklades. Iterativ-adaptiv-metoden för amplitud- och fasskattning (IAA-APES) från gruppantennsignalbehandling användes också för sudoku för att utnyttja glesheten i sudokulösningen på liknande sätt som i mättillämpningen. LIKES och SPICE testades också för sudokuproblemet och resultaten jämfördes med l1-norm-minimiering, viktad l1- norm, och sinkhorn-balancering. SPICE och l1-norm är ekvivalenta i termer av prestanda men SPICE är långsammare. LIKES och viktad l1-norm är ekvivalenta och har bättre noggrannhet än SPICE och l1- norm. SDR visade sig ha bäst prestanda för sudoku med unika lösningar, men SDR är också den metod med beräkningsmässigt högst komplexitet. Prestandan för IAA-APES ligger någonstans mellan SPICE och LIKES men är snabbare än bägge dessa.