### Abstract

Original language | English |
---|---|

Title of host publication | INFOCOMP 2016, The Sixth International Conference on Advanced Communications and Computation |

Editors | Claus-Peter Rückemann, Malgorzata Pankowska |

Publisher | IARIA |

Pages | 12-17 |

ISBN (Print) | 978-1-61208-478-7 |

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

Conference | 6th International Conference on Advanced Communications and Computation (INFOCOMP 2016) |
---|---|

Abbreviated title | INFOCOMP 2016 |

Country | Spain |

City | Valencia |

Period | 22/05/16 → 26/05/16 |

### Fingerprint

### Keywords

- Artificial intelligence
- Operations research
- Solution of a Killer Samurai Soduku Puzzle as an Optimization Problem
- Mathematical programming
- Mixed Integer Linear Programming

### Cite this

*INFOCOMP 2016, The Sixth International Conference on Advanced Communications and Computation*(pp. 12-17). IARIA.

}

*INFOCOMP 2016, The Sixth International Conference on Advanced Communications and Computation.*IARIA, pp. 12-17, 6th International Conference on Advanced Communications and Computation (INFOCOMP 2016), Valencia, Spain, 22/05/16.

**A Novel MILP Model to Solve Killer Samurai Sudoku Puzzles.** / Fonseca, José Barahona da.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A Novel MILP Model to Solve Killer Samurai Sudoku Puzzles

AU - Fonseca, José Barahona da

PY - 2016/5/22

Y1 - 2016/5/22

N2 - 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.

AB - 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.

KW - Artificial intelligence

KW - Operations research

KW - Solution of a Killer Samurai Soduku Puzzle as an Optimization Problem

KW - Mathematical programming

KW - Mixed Integer Linear Programming

M3 - Conference contribution

SN - 978-1-61208-478-7

SP - 12

EP - 17

BT - INFOCOMP 2016, The Sixth International Conference on Advanced Communications and Computation

A2 - Rückemann, Claus-Peter

A2 - Pankowska, Malgorzata

PB - IARIA

ER -