Home // INFOCOMP 2016, The Sixth International Conference on Advanced Communications and Computation // View article
Authors:
Jose Fonseca
Keywords: Artificial Intelligence, Operations Research, Solution of a Killer Samurai Soduku Puzzle as an Optimization Problem, Mathematical Programming, Mixed Integer Linear Programming
Abstract:
The first problems solved by Artificial Intelligence were toy problems, games and more recently puzzles. In the eighties there were annual tournaments of chess computer programs and Kasparov was even defeated by one of these chess programs. More recently Sudoku appeared in Japan and then Kakuro and Killer Sudoku puzzles that were rapidly disseminated through the rest of the world. More recently arose the Killer Samurai Sudoku puzzles that consist of five Killer Sudoku puzzles with the fifth puzzle overlapping over the remaining four puzzles. As an alternative approach to AI, in this work we formulate the Killer Sudoku puzzle problem solution as an optimization problem with constraints in the framework of a Mixed Integer Linear Program (MILP) model and then solve it using the Cplex solver with the GAMS software. A Killer Sudoku puzzle consists of a matrix of dimension 9x9 where each line and column must be a permutation of integers between 1 and 9, each sub-matrix 3x3 must be a permutation of these numbers and there are a set of colour areas or cages that must have a predefined sum. The runtimes of the solution of a black belt Killer Sudoku puzzle using our MILP model were very small, just some few seconds. To our knowledge this is the first proposal to solve a Killer Sudoku puzzle with a linear MILP model, using the Cplex solver.
Pages: 12 to 17
Copyright: Copyright (c) IARIA, 2016
Publication date: May 22, 2016
Published in: conference
ISSN: 2308-3484
ISBN: 978-1-61208-478-7
Location: Valencia, Spain
Dates: from May 22, 2016 to May 26, 2016