Solving Hitori
Applying Answer Set Programming to Hitori
S. de Nooij (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 investigate the performance of modelling and solving paradigms on the NP-complete puzzle Hitori. The choice of paradigm can have a significant impact on performance, but it is not always clear which paradigm is most suitable and why. We develop an ASP model to compare to models made in other paradigms. We investigate the effect of redundant constraints and research the effects of different puzzle properties on the solving time of our ASP model. In our experimental evaluation, we compare the ASP model to the models in otherparadigms from parallel studies. We find that redundant constraints have a negat-ve impact on performance. The solving times ofthe ASP model had little variance and was not or slightly correlated with various puzzle properties. Our results show that our approach solves 50-by-50 puzzles 38 times faster at PAR-2 than the second-best model and is the only model that never exceeds the specified timeout, showing the suitability of ASP to Hitori.
https://github.com/sappho3/Thesis-Hitori-shared
https://github.com/sappho3/Thesis-Hitori-ASP