A Novel MILP Model to Solve Killer Samurai Sudoku Puzzles

Research output: Chapter in Book/Report/Conference proceedingConference contribution

131 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationINFOCOMP 2016, The Sixth International Conference on Advanced Communications and Computation
EditorsClaus-Peter Rückemann, Malgorzata Pankowska
PublisherIARIA
Pages12-17
ISBN (Print)978-1-61208-478-7
Publication statusPublished - 22 May 2016
Event6th International Conference on Advanced Communications and Computation (INFOCOMP 2016) - Valencia, Spain
Duration: 22 May 201626 May 2016
Conference number: 6th

Conference

Conference6th International Conference on Advanced Communications and Computation (INFOCOMP 2016)
Abbreviated titleINFOCOMP 2016
CountrySpain
CityValencia
Period22/05/1626/05/16

Keywords

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

Fingerprint Dive into the research topics of 'A Novel MILP Model to Solve Killer Samurai Sudoku Puzzles'. Together they form a unique fingerprint.

  • Cite this

    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.