A novel linear milp model to solve kakuro puzzles

José Barahona da Fonseca, DEE Group Author

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

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.
Original languageUnknown
Title of host publicationProceedings of Controlo 2012 Conference
Pages54-60
Publication statusPublished - 1 Jan 2012
EventControlo 2012 -
Duration: 1 Jan 2012 → …

Conference

ConferenceControlo 2012
Period1/01/12 → …

Cite this

Fonseca, J. B. D., & DEE Group Author (2012). A novel linear milp model to solve kakuro puzzles. In Proceedings of Controlo 2012 Conference (pp. 54-60)