Smashing Hitori
An analysis of the strengths and weaknesses of constraint programming paradigm Pumpkin
L. Smits (TU Delft - Electrical Engineering, Mathematics and Computer Science)
A.L.D. Latour – Mentor (TU Delft - Algorithmics)
T.J. Coopmans – Mentor (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
Logic-based puzzle solving serves as a standard benchmark for evaluating computational paradigms; however, comparisons are frequently biased by the researcher’s familiarity with specific tools. To ensure an objective evaluation, we contribute to a collaborative benchmarking effort by analysing the suitability of the Constraint Satisfaction Problem (CSP) paradigm for solving the puzzle Hitori. Specifically, we use PUMPKIN [5]. Our results show that redundant constraints can have a positive impact on solve time, particularly when using a Lazy constraint strategy where dynamic constraint generation is employed. Additionally, our analysis of puzzle characteristics reveals that the Lazy strategy benefits significantly from high counts of non-adjacent duplicates, while the Distance strategy proves sensitive to deviations in the total black cell count. We demonstrate that this Lazy strategy significantly outperforms the Distance strategy, offering superior scalability with respect to puzzle size. Furthermore, in a comparative analysis against other computational paradigms, our solver proved more efficient than LP (GUROBI), Prolog, and SMT (Z3) implementations, ultimately ranking second, surpassed only by ASP (CLASP). This establishes CSP, specifically with the Lazy strategy, as a competitive approach for modelling and solving Hitori.