The Algorithm Selection Problem for Solving Sudoku with Metaheuristics

In this paper we study the algorithm selection problem and instance space analysis for solving Sudoku puzzles with metaheuristic algorithms. We formulate Sudoku as a combinatorial optimisation problem and implement four local-search metaheuristics to solve the problem instances. A feature space is constructed and instance space analysis (ISA) methodology is applied to this problem for the first time. The aim is to use ISA to determine how these features affect the performance of the algorithms and how they can be used for automated algorithm selection. We also consider algorithm selection using multinomial logistic regression models with l1-penalty for comparison. Different algorithm performance metrics are considered and we found that the choice of these metrics affected whether the use of ISA was worthwhile. We found that when the performance of metaheuristic solvers is similar, predicting whether an algorithm will perform 'well' is also useful.