Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Solving Sudoku by Sparse Signal Processing
KTH, Skolan för elektro- och systemteknik (EES), Signalbehandling.
2015 (Engelska)Självständigt arbete på avancerad nivå (masterexamen), 20 poäng / 30 hpStudentuppsats (Examensarbete)
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.

Ort, förlag, år, upplaga, sidor
2015. , s. 47
Serie
EES Examensarbete / Master Thesis ; XR-EE-SB 2015:001
Nationell ämneskategori
Annan elektroteknik och elektronik
Identifikatorer
URN: urn:nbn:se:kth:diva-160908OAI: oai:DiVA.org:kth-160908DiVA, id: diva2:792205
Utbildningsprogram
Teknologie masterexamen - Trådlösa system
Examinatorer
Tillgänglig från: 2015-03-03 Skapad: 2015-03-03 Senast uppdaterad: 2015-03-03Bibliografiskt granskad

Open Access i DiVA

fulltext(1708 kB)2499 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 1708 kBChecksumma SHA-512
7fe354ba80f9f138b8e9395678b95ac327a4d1e8d3b641fa8112b76bbff78961af6a5d5f8dd6884851e4c27b6a5af10d6165357122408e95950efc9bdddb37a4
Typ fulltextMimetyp application/pdf

Av organisationen
Signalbehandling
Annan elektroteknik och elektronik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 2499 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 2399 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf