A Novel MILP Model to Solve Killer Samurai Sudoku Puzzles

Abstract

A Killer Samurai Sudoku puzzle is a NP-Hard problem and very nonlinear since it implies the comparison of areas or cages sums with their desired values, and humans have a lot of difficulty to solve these puzzles. On the contrary our mixed integer linear programming (MILP) model, using the Cplex solver, solves easy puzzles in few seconds and hard puzzles in few minutes. We begin to explain why humans have such a great difficulty to solve Killer Samurai Sudoku puzzles, even for low level of difficulty ones, taking into account the cognitive limitations as the very small working memory of 7-8 symbols. Then we briefly review our previous work where we describe linearization techniques that allow solving any nonlinear problem with a linear MILP model [1]. Next we describe the sets of constraints that define a Killer Sudoku puzzle and the definition of the objective variable and the implementation of the solution of a Killer Samurai Sudoku puzzle as a minimization problem formulated as a MILP model and implemented with the GAMS software. Finally we present the solutions of a hard Killer Samurai Sudoku puzzles with our MILP model using the Cplex solver.