The Eternal Battle between Determinism and Nondeterminism: preliminary Studies in the Sudoku Domain

Declarative formalisms such as Answer Set Programming (ASP) allow concise and intuitive problem modelling, often at the price of an inefficient evaluation over large search spaces. However, ASP encodings can be enriched with domain-specific knowledge aimed at tailoring the search space, e.g. by “suggesting” deterministic consequences to solvers; nonetheless, it is not obvious whether, and when, adding such information pays off in terms of performance. In this paper we investigate this issue in the Sudoku domain, that represents the ideal setting for such a study: indeed, one can model (a) solutions that deeply rely on non-determinism (e.g., a “pure” guess&check paradigm), (b) solutions featuring deterministic inference rules implementing the knowledge of skilled players, and (c) hybrid combinations thereof.