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 . 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.
|Title of host publication||INFOCOMP 2016, The Sixth International Conference on Advanced Communications and Computation|
|Editors||Claus-Peter Rückemann, Malgorzata Pankowska|
|Publication status||Published - 22 May 2016|
|Event||6th International Conference on Advanced Communications and Computation (INFOCOMP 2016) - Valencia, Spain|
Duration: 22 May 2016 → 26 May 2016
Conference number: 6th
|Conference||6th International Conference on Advanced Communications and Computation (INFOCOMP 2016)|
|Abbreviated title||INFOCOMP 2016|
|Period||22/05/16 → 26/05/16|
- Artificial intelligence
- Operations research
- Solution of a Killer Samurai Soduku Puzzle as an Optimization Problem
- Mathematical programming
- Mixed Integer Linear Programming
Fonseca, J. B. D. (2016). A Novel MILP Model to Solve Killer Samurai Sudoku Puzzles. In C-P. Rückemann, & M. Pankowska (Eds.), INFOCOMP 2016, The Sixth International Conference on Advanced Communications and Computation (pp. 12-17). IARIA.