Change search
ReferencesLink to record
Permanent link

Direct link
Performance and Scalability of Sudoku Solvers
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2013 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesisAlternative title
Prestanda och Skalbarhet för Sudoku Lösare (Swedish)
Abstract [en]

This paper aims to clarify the differences in algorithm design

with a goal of solving sudoku. A few algorithms were

chosen suitable to the problem, yet different from one another.

To take an everyday puzzle and utilize common computer

science algorithms and learn more about them. Get

relevant data to see how they perform in situations, how

easily they can be modified and used in larger sudokus.

Also how their performance scales when the puzzle grows


From the results Dancing links was the fastest and scaled

best of the algorithms tested, while Brute-force and Simulated

annealing struggled keeping consistent results.

Abstract [sv]

Detta dokument syftar till att klargöra skillnaderna i algoritmer

med målet att lösa sudoku. Välja ett par olika algorithmer

lämpliga för problemet, men som samtidigt skiljer

sig från varandra. Att ta ett dagligt pussel och utnyttja vanligt

förekommande algoritmer inom datavetenskap och lära

sig mer om dem. Få relevant data och se hur de presterar i

olika situationer, hur lätt de kan modifieras och användas i

större Sudokus. Även hur deras prestanda skalar när pusslet

blir större.

Dancing links var den snabbaste algoritmen och skalade

bäst av de som testades. Brute-force och Simulated annealing

inte var lika konsekventa genom alla tester och betydligt

långsammare i överlag.

Place, publisher, year, edition, pages
Kandidatexjobb CSC, K13004
National Category
Computer Science
URN: urn:nbn:se:kth:diva-134823OAI: diva2:668236
Educational program
Master of Science in Engineering - Computer Science and Technology
Available from: 2013-12-13 Created: 2013-11-29 Last updated: 2013-12-13Bibliographically approved

Open Access in DiVA

Performance and Scalability of Sudoku Solvers(664 kB)142 downloads
File information
File name FULLTEXT01.pdfFile size 664 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links
By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 142 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

Total: 126 hits
ReferencesLink to record
Permanent link

Direct link