Patrik Berggren and David Nilsson

A study of Sudoku solving algorithms

Abstract

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.