Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • 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.
Series
EES Examensarbete / Master Thesis, XR-EE-SB 2015:001
National Category
Other Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-160908OAI: oai:DiVA.org:kth-160908DiVA: diva2:792205
Educational program
Master of Science - Wireless Systems
Examiners
Available from: 2015-03-03 Created: 2015-03-03 Last updated: 2015-03-03Bibliographically approved

Open Access in DiVA

fulltext(1708 kB)1858 downloads
File information
File name FULLTEXT01.pdfFile size 1708 kBChecksum SHA-512
7fe354ba80f9f138b8e9395678b95ac327a4d1e8d3b641fa8112b76bbff78961af6a5d5f8dd6884851e4c27b6a5af10d6165357122408e95950efc9bdddb37a4
Type fulltextMimetype application/pdf

By organisation
Signal Processing
Other Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 1858 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 1066 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf