Change search
ReferencesLink to record
Permanent link

Direct link
A study of Sudoku Solving Algorithms.
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2012 (English)Independent thesis Advanced level (professional degree), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

In this bachelor thesis three different Sudoku solving algorithms are studied. The study is primarily concerned with solving ability, but also includes the following: difficulty rating, puzzle generation ability, and suitability for parallelizing. These aspects are studied for individual algorithms but are also compared between the different algorithms. The evaluated algorithms are backtrack, rule-based and Boltzmann machines. Measurements are carried out by measuring the solving time on a database of 17-clue puzzles, with easier versions used for the Boltzmann machine. Results are presented as solving time distributions for every algorithm, but relations between the algorithms are also shown. We conclude that the rule-based algorithm is by far the most efficient algorithm when it comes to solving Sudoku puzzles. It is also shown that some correlation in difficulty rating exists between the backtrack and rule-based algorithms. Parallelization is applicable to all algorithms to a varying extent, with clear implementations for search-based solutions. Generation is shown to be suitable to implement using deterministic algorithms such as backtrack and rule-based.

Abstract [sv]

Den här exjobbsrapporten på kandidatnivå presenterar tre olika lösningsalgoritmer för Sudoku. Studiens huvudsyfte är att studera lösningsprestanda men analyserar även svårighetsgrad, möjligheter till generering och parallelisering. Samtliga aspekter studeras för varje algoritm och jämförs även mellan enskilda algoritmer. De utvalda algoritmerna är backtrack, regelbaserad och Boltzmann-maskiner. Samtliga mätningar görs på en databas med pussel som har 17 ledtrådar, med vissa anpassningar för Boltzmann-maskiner. Resultaten presenteras med fördelningar som visar lösningstider för varje algoritm separat. Slutsatsen är att regelbaserade lösare är effektivast på att lösa Sudokupussel. En korrelation mellan den regelbaserades och den backtrack-baserade lösares svårighetsrating visas. Parallelisering visas vara tillämpbart till olika grad för de olika algoritmerna och är enklast att tillämpa på sökbaserade lösare. Generering konstateras vara lättast att implementera med deterministiska algoritmer som backtrack och rule-based.

Place, publisher, year, edition, pages
Kandidatexjobb CSC, K12011
National Category
Computer Science
URN: urn:nbn:se:kth:diva-131015OAI: diva2:654461
Educational program
Master of Science in Engineering - Computer Science and Technology
Available from: 2013-10-07 Created: 2013-10-07

Open Access in DiVA

No full text

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

Search outside of DiVA

GoogleGoogle Scholar
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: 89 hits
ReferencesLink to record
Permanent link

Direct link