A Novel MILP Model to Solve Killer Samurai Sudoku Puzzles

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

83 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

Fingerprint

Linear programming
Linearization
Computational complexity
Data storage equipment

Keywords

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

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.
Fonseca, José Barahona da. / A Novel MILP Model to Solve Killer Samurai Sudoku Puzzles. INFOCOMP 2016, The Sixth International Conference on Advanced Communications and Computation. editor / Claus-Peter Rückemann ; Malgorzata Pankowska. IARIA, 2016. pp. 12-17
@inproceedings{139681fc87474936ad1d97425ea6f98f,
title = "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.",
keywords = "Artificial intelligence, Operations research, Solution of a Killer Samurai Soduku Puzzle as an Optimization Problem, Mathematical programming, Mixed Integer Linear Programming",
author = "Fonseca, {Jos{\'e} Barahona da}",
year = "2016",
month = "5",
day = "22",
language = "English",
isbn = "978-1-61208-478-7",
pages = "12--17",
editor = "R{\"u}ckemann, {Claus-Peter } and Pankowska, {Malgorzata }",
booktitle = "INFOCOMP 2016, The Sixth International Conference on Advanced Communications and Computation",
publisher = "IARIA",

}

Fonseca, JBD 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. 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.

INFOCOMP 2016, The Sixth International Conference on Advanced Communications and Computation. ed. / Claus-Peter Rückemann; Malgorzata Pankowska. IARIA, 2016. p. 12-17.

Research output: Chapter in Book/Report/Conference proceedingConference 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 -

Fonseca JBD. A Novel MILP Model to Solve Killer Samurai Sudoku Puzzles. In Rückemann C-P, Pankowska M, editors, INFOCOMP 2016, The Sixth International Conference on Advanced Communications and Computation. IARIA. 2016. p. 12-17