Algorithm selection using machine learning for sudoku puzzles

Abstract

Sudokus sind kombinatorische Zahlenrätsel, welche regelmäßig in Zeitschriften, Zeitungen und auf Webseiten erscheinen und zum Brainstorming gut geeignet sind. Diese kombinatorischen Zahlenrätsel sind als eine quadratische Matrix mit Zeilen-, Spalten- und Untergitterbeschränkungen definiert, wobei die Untergitter als die Quadratwurzel der Matrixgröße definiert sind. Im Allgemeinen sind Sudoku-Rätsel Spezialfälle von sogenannten lateinischen Quadraten.Sudoku-Rätsel sind rechnerisch NP-komplette Probleme, d.h. nach dem No-Free-Lunch-Theorem gibt es keinen einzigen Algorithmus, der alle Instanzen der Sudoku-Rätsel am effizientesten löst. Daraus ergibt sich die Frage zur Algorithmenauswahl, bei der nicht für jedes Rätsel ein neuer Algorithmus geschrieben werden muss, sondern der beste Algorithmus aus einer gegebenen Liste von Algorithmen mit guter Leistung ausgewählt werden kann. Darüber hinaus ist es möglicherweise auch wichtig, die Laufzeit von Algorithmen für jedes Sudoku-Rätsel abzuschätzen.In dieser Arbeit untersuchen wir das Problem der Algorithmenauswahl und Laufzeitvorhersage für Sudoku-Rätsel mit Methoden des maschinellen Lernens. Wir identifizieren vier Sudoku-Solver nach aktuellem Stand der Technik, um die Problemstellung der Algorithmenauswahl und Laufzeitvorhersage anzugehen. Zusätzlich wurde die Berechnung von 70 Merkmalen durchgeführt. Für jede Fragestellung wurden fünf Klassifizierungs- und sechs Regressionsmethoden, zusammen mit der Merkmalselektion, der Datendiskretisierung und verschiedenen Parametereinstellungen untersucht. Abschließend lässt sich sagen, dass die von uns erstellte Umgebung -bezogen auf die Frage der statischen Algorithmenauswahl und Laufzeitvorhersage für Sudoku-Rätsel – robust in Bezug auf Genauigkeit der Algorithmenauswahl und gut bei der Vorhersage der Laufzeit ist.

Sudokus are interesting puzzles for brainstorming and appear regularly in magazines, papers and websites. These puzzles are defined as a square matrix having a row, column and sub-grid constraints, where the sub-grids are the square root of the matrix size. In general, Sudoku puzzles are special cases of Latin squares. Computationally, Sudoku puzzles are NP-complete problems, i.e., according to the No Free Lunch Theorem, there is no single algorithm that solves all instances of the Sudoku puzzles most efficiently. This gives rise to the question of algorithm selection, where there is no requirement of writing a new algorithm for every puzzle but the best performing algorithm can be chosen from a given set of good performing algorithms. Moreover, it may also be of importance knowing how long to run an algorithm. In this thesis, we investigate the algorithm selection and run-time prediction problem for Sudoku puzzles using machine learning methods. We identify four state-of-the-art Sudoku solvers for algorithm Selection and run-time Prediction. Additionally, identification and computation of 70 features for characterizing Sudoku puzzles distinctively was done. Five classification and six regression methods for each of the problem statements have been investigated along with feature selection method, discretization of data and various parameter settings.Finally, the environment built by us for algorithm selection and run-time prediction for Sudoku puzzles was robust in terms of accuracy for algorithm selection and good in predicting the run-time.