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
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
Identifiers
URN: urn:nbn:se:kth:diva-146016OAI: oai:DiVA.org:kth-146016DiVA: diva2:721641
Subject / course
Computer Science
Educational program
Bachelor of Science in Engineering - Computer Engineering
Supervisors
Examiners
Available from: 2014-11-25 Created: 2014-06-04 Last updated: 2014-11-25Bibliographically approved

Open Access in DiVA

fulltext(678 kB)1276 downloads
File information
File name FULLTEXT01.pdfFile size 678 kBChecksum SHA-512
b391fa6c03af2d4f569230572f4cd3994817144d04be9db59885a7357773bc4b95bfd5781fb95759173d9b3827932df27030cda9cddb5055864804fcd97409dd
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: 1276 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: 300 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