Scaling of popular Sudoku solving algorithms

Abstract: In this bachelor thesis we study 6 popular Sudoku solving algorithms, found through Google, to find the algorithm that has the slowest growth. The algorithms we tested are: brute-force, a pen-and-paper method, two exact cover reductions in Python and Haskell, a SAT reduction, and a constraint satisfaction algorithm. The algorithms were tried by solving Sudoku puzzles of sizes n = {2, 3, 4, 5} where we measured the solution time. We conclude that the slowest growing algorithm, by far, is the SAT reduction, followed by the exact cover reductions. Brute-force grows, unsurprisingly, the fastest.