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

INFORMS Transactions on Education

ArnaudMalapert¹ 

关键词: puzzles;    constraint programming;    teaching modeling;    teaching optimization;   

DOI  :  10.1287/ited.2017.0193

学科分类：社会科学、人文和艺术（综合）

来源: INFORMS

【 摘 要 】

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.

【 授权许可】

CC BY