The backtracking algorithm and diﬀerent representations for solving Sudoku Puzzles
Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
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 diﬀerent 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 beneﬁt over a n2 representation; (2) a greedy heuristic approach has superior worst case times but worse best case, and n3 representations sees great beneﬁts 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.
IdentifiersURN: urn:nbn:se:kth:diva-146016OAI: oai:DiVA.org:kth-146016DiVA: diva2:721641
Subject / course
Bachelor of Science in Engineering - Computer Engineering