Eating Soup with a Fork: Solving Hitori with Integer Linear Programming
An Investigation into the Suitability of Integer Linear Programming for Solving Single-Solution Hitori Instances
S. van Luenen (TU Delft - Electrical Engineering, Mathematics and Computer Science)
A.L.D. Latour – Mentor (TU Delft - Algorithmics)
T.J. Coopmans – Graduation committee member (TU Delft - QCD/Coopmans Group)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
We study the advantages and disadvantages of using Integer Linear Programming for solving instances of the NP-complete puzzle Hitori. We do so as part of a larger comparison between different modelling-and-solving (M&S) paradigms that aims to find what solving techniques do (not) work for different paradigms so as to guide effective modelling. To this end we create three models: a path model that is quartic with regards to instance size, a quadratic and probabilistic optimised naive model, and an exponential duplicates model which uses proven properties of the game. We measure their runtime performance with and without different optimisations on 1000 10 x 10 Hitori instances, compare it to the runtime performance of models in four other M&S paradigms, and correlate properties of puzzle instances to runtime. We find that there is no performance difference between our optimised naive and duplicates models though our path model is significantly slower. Adding redundant constraints tends to slow models down. Our optimised naive model performs better than a Logic Programming model, but worse than a Satisfiability Modulo Theories, a Constraint Satisfaction Problem, and an Answer Set Programming model. Runtime correlates strongly with the number of non-unique tiles in the problem instance, though the correlation's direction differs per model. We conclude that ILP is an unintuitive and slow tool for solving Hitori instances, especially when compared to other M&S paradigms.