Scaling of popular Sudoku solving algorithms

University essay from KTH/Skolan för datavetenskap och kommunikation (CSC); KTH/Skolan för datavetenskap och kommunikation (CSC)

Author: Markus Videl; Mattias Palo; [2014]

Keywords: ;

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.

  AT THIS PAGE YOU CAN DOWNLOAD THE WHOLE ESSAY. (follow the link to the next page)