Paper Info
Title
Puzzle - Solving the -Fractions Puzzle as a Constraint Programming Problem.
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.
Year
DOI
Venue
2018
10.1287/ited.2017.0193
INFORMS Trans. Education
DocType
Volume
Issue
Journal
19
1
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
Arnaud Malapert1314.50
Julien Provillard2516.08