Title: A novel linear milp model to solve kakuro puzzles
Authors: José Fonseca xix
Abstract: It is shown that a Kakuro puzzle is a NP-Hard problem and very nonlinear since it implies the comparison of segment sums with their desired values, and humans have a lot of difficulty to solve Kakuro puzzles. By the contrary our mixed integer linear programming (MILP) model, using the Cplex solver, solves very hard puzzles in a fraction of a second. We begin to explain why humans have a so great difficulty to solve Kakuro puzzles, even for low level of difficulty ones. Then we review briefly our previous work where we describe linearization techniques that allow solving any nonlinear problem with a MILP model. Next we describe the constraints and their implementation with the GAMS software and finally we compare the runtimes of our MILP model with previous MILP models using a black belt Kakuro puzzle.
Publication date: 2012-07-16
Online entry date: 2013-05-08
Conference: CONTROLO’2012
Publication pdf: Click for full publication