Change search
CiteExportLink to record
Permanent link

Direct link
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Solving Sudoku by Sparse Signal Processing
KTH, School of Electrical Engineering (EES), Signal Processing.
2015 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

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.

Abstract [sv]

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.

Place, publisher, year, edition, pages
2015. , 47 p.
EES Examensarbete / Master Thesis, XR-EE-SB 2015:001
National Category
Other Electrical Engineering, Electronic Engineering, Information Engineering
URN: urn:nbn:se:kth:diva-160908OAI: diva2:792205
Educational program
Master of Science - Wireless Systems
Available from: 2015-03-03 Created: 2015-03-03 Last updated: 2015-03-03Bibliographically approved

Open Access in DiVA

fulltext(1708 kB)