Change search
ReferencesLink to record
Permanent link

Direct link
The backtracking algorithm and different representations for solving Sudoku Puzzles
KTH, School of Computer Science and Communication (CSC).
KTH, School of Computer Science and Communication (CSC).
2014 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Two implementations of the backtracking algorithm for solving Sudoku puzzles as well as their dependence on the representations of the problem have been studied in order to ascertain pros and cons of different approaches. For each backtracking step, empty cells could be assigned numbers sequentially or, by using a greedy heuristic, by the probability that guessed numbers were more likely to be correct. Representations of the Sudoku puzzles varied from a n2 matrix to a n3 matrix, as well as a combination of both. This study shows that (1) a sequential approach has better best case times but poor worst case behaviour, and a n3 representation does not benefit over a n2 representation; (2) a greedy heuristic approach has superior worst case times but worse best case, and n3 representations sees great benefits over n2 representations. A combination of n2 and n3 representations grants the best overall performance with both approaches.

Place, publisher, year, edition, pages
2014. , 50 p.
National Category
Computer Science
URN: urn:nbn:se:kth:diva-146016OAI: diva2:721641
Subject / course
Computer Science
Educational program
Bachelor of Science in Engineering - Computer Engineering
Available from: 2014-11-25 Created: 2014-06-04 Last updated: 2014-11-25Bibliographically approved

Open Access in DiVA

fulltext(678 kB)724 downloads
File information
File name FULLTEXT01.pdfFile size 678 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Ekström, Johan
By organisation
School of Computer Science and Communication (CSC)
Computer Science

Search outside of DiVA

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

Direct link