prob041: The n-Fractions Puzzle

proposed by Alan Frisch, Christopher Jefferson, Ian Miguel, Toby Walsh
frisch@cs.york.ac.uk, caj@cs.york.ac.uk, ianm@cs.york.ac.uk, tw@4c.ucc.ie

Modelling

An easy way to avoid rounding errors, is to multiply up the fractions. In the case of the 3-fractions puzzle, this gives: 
A(EF)(HI)+D(BC)(HI)+G(BC)(EF) == (BC)(EF)(HI)
Given the repetition of the original denominators, it is now useful to bind each of these to an auxiliary variable for greater propagation.

When n is less than or equal to 3, an all-different constraint can be used on the digit variables. Otherwise, an occurrence constraint is used to ensure that each digit appears the correct number of times.

Symmetry-breaking and Implied Constraints

Symmetry in the n-fractions puzzle stems from the commutativity of the sum operator. An obvious way to break this symmetry is to order the fractions. For example, in the 3-fractions puzzle: 
A     D     G
-- <= -- <= --
BC    EF    HI
It is also possible to view the fractions arranged in a matrix model. Again using the 3-fractions puzzle as an example: 
/A D G\
|B E H|
\C F I/
This matrix has column symmetry only, hence all symmetry can be broken by lexicographically ordering the columns [1]. Due to the structure of the problem, different results are obtained by changing the order in which the column vectors are built. For example, instead of reading the elements top to bottom, producing <A, B, C>, <D, E, F> and <G, H, I>, the elements can be read <C, B, A>, <F, E, D> and <I, H, G>. Depending on the choice of symmetry-breaking constraints, a variety of implied constraints follow, as discussed in [2] below.
  1. P. Flener, A.M. Frisch, B. Hnich, Z. Kiziltan, I. Miguel, J. Pearson, T. Walsh. Breaking Row and Column Symmetries in Matrix Models. Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, 462--476, 2002.
  2. A.M. Frisch, C. Jefferson, I. Miguel. Symmetry-breaking as a Prelude to Implied Constraints: A Constraint Modelling Pattern. APES Technical Report 75-2003.