Puzzle—Solving the n -Fractions Puzzle as a Constraint Programming Problem

Arnaud Malapert () and Julien Provillard ()
Additional contact information
Arnaud Malapert: Université Côte d’Azur, CNRS, I3S, France
Julien Provillard: Université Côte d’Azur, CNRS, I3S, France

INFORMS Transactions on Education, 2018, vol. 19, issue 1, 48-55

Abstract: The aim in solving puzzles is to find the solution using several clues and restrictions. In this paper, we solve a numerical puzzle, the n -fractions puzzle, by constraint programming. The n-fractions puzzle is problem 41 of the CSPLib, a library of test problems for constraint solvers. Models referenced in the CSPLib return invalid solutions as soon as the number n of fractions exceeds five. To solve the n -fractions puzzle, we first provide an upper bound for the unsatisfiability inspired by constraint filtering techniques. Then we propose two new constraint programming models that exploit the integer factorization of the fractions’ denominators and their lowest common multiple. The proposed models can solve up to the 19-fractions puzzle within a few minutes and without returning invalid solutions. Some restrictions of the models that eliminate invalid solutions still allow them to solve larger n -fractions puzzles, even if the solving times increase. At the end, only six n-fractions puzzles remain open.

Keywords: puzzles; constraint programming; teaching modeling; teaching optimization (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/ited.2017.0193 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orited:v:19:y::i:1:p:48-55

Access Statistics for this article

More articles in INFORMS Transactions on Education from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().