% % The n-Fractions Puzzle % % Sample ECLiPSe solution by Joachim Schimpf, 2019 % under Creative Commons Attribution 4.0 International License. % % % This is problem 41 in CSPLIB (http://csplib.org/Problems/prob041) % % Original fractions puzzle: Find 9 distinct non-zero digits that satisfy: % % A D G % -- + -- + -- == 1 % BC EF HI % % Generalisation: Find 3n non-zero digits satisfying % % 1 = \sum_{i \in 1..n} x_i / y_iz_i % % where y_iz_i is shorthand for 10y_i+z_i and the number of occurrences % of each digit in 1..9 is between 1 and ceil(n/3). % % We ignore symmetric solutions caused by commutativity of addition. % % % N=3 has a unique solution, N=4 has 1384 solutions. % First solutions for various N: % 3 : [[5, 3, 4], [7, 6, 8], [9, 1, 2]] % 4 : [[1, 2, 4], [3, 5, 6], [8, 1, 4], [9, 2, 7]] % 5 : [[1, 1, 2], [5, 4, 5], [8, 3, 6], [9, 2, 7], [9, 3, 6]] % 6 : [[1, 1, 2], [3, 7, 6], [6, 4, 5], [8, 3, 8], [9, 2, 7], [9, 4, 5]] % 7 : [[1, 1, 1], [2, 2, 2], [3, 3, 6], [7, 3, 5], [8, 4, 8], [9, 4, 4], [9, 5, 5]] % 8 : [[1, 1, 1], [2, 2, 2], [3, 3, 3], [6, 4, 5], [7, 7, 7], [8, 4, 8], [9, 4, 5], [9, 6, 6]] % 9 : [[1, 1, 1], [2, 2, 2], [3, 3, 3], [4, 5, 5], [6, 4, 8], [7, 7, 7], [9, 4, 5], [9, 6, 6], [9, 8, 8]] % 10 : [[1, 1, 1], [1, 2, 2], [2, 2, 3], [3, 3, 3], [4, 4, 4], [5, 5, 5], [7, 4, 6], [8, 8, 8], [9, 6, 9], [9, 6, 9]] % 11 : [[1, 1, 1], [1, 2, 2], [2, 2, 3], [3, 3, 3], [4, 4, 4], [4, 5, 5], [6, 5, 5], [6, 7, 8], [7, 7, 8], [8, 6, 9], [9, 6, 9]] % 12 : [[1, 1, 1], [1, 2, 2], [2, 2, 3], [3, 3, 3], [4, 4, 4], [4, 7, 8], [5, 6, 9], [5, 6, 9], [5, 8, 8], [7, 5, 6], [7, 6, 9], [9, 7, 8]] % 13 : [[1, 1, 1], [1, 1, 2], [2, 2, 2], [2, 3, 3], [3, 3, 3], [4, 4, 4], [4, 4, 8], [5, 5, 5], [5, 7, 7], [5, 8, 8], [6, 9, 6], [6, 9, 6], [7, 9, 8]] % 14 : [[1, 1, 1], [1, 1, 2], [2, 2, 2], [2, 3, 3], [3, 3, 3], [4, 4, 4], [4, 6, 6], [4, 6, 6], [5, 7, 7], [5, 8, 8], [5, 8, 8], [5, 9, 9], [7, 9, 8], [7, 9, 9]] % 15 : [[1, 1, 1], [1, 1, 2], [2, 2, 2], [2, 3, 3], [3, 3, 3], [4, 5, 6], [4, 7, 8], [4, 7, 8], [4, 9, 6], [4, 9, 9], [5, 7, 7], [5, 7, 8], [5, 8, 8], [5, 9, 9], [6, 6, 6]] % 16 : [[1, 1, 1], [1, 1, 1], [2, 2, 2], [2, 2, 2], [3, 3, 3], [3, 4, 4], [3, 6, 6], [3, 8, 8], [4, 9, 6], [4, 9, 6], [4, 9, 6], [4, 9, 8], [5, 7, 7], [5, 7, 7], [5, 9, 8], [5, 9, 8]] % :- lib(ic). :- lib(ic_global). nfractions(N, Triplets) :- ( for(_,1,N), foreach([A,B,C], Triplets), foreach(A/(10*B+C), Terms) do [A,B,C] #:: 1..9 ), sum(Terms) $= 1, lists:append(Triplets, Digits), ( for(I,1,9), param(Digits,N) do occurrences(I, Digits, NOcc), NOcc #:: 1..integer(ceiling(N/3)) ), ( fromto(Triplets,[Ti,Tj|Ts],[Tj|Ts],[_]) do lex_le(Ti, Tj) ), labeling(Digits). % Simpler code, for the N=3 case only fractions(Digits) :- Digits = [A,B,C,D,E,F,G,H,I], Digits #:: 1..9, A/(10*B+C) + D/(10*E+F) + G/(10*H+I)$= 1, ic:alldifferent(Digits), lex_le([A,B,C], [D,E,F]), % eliminate symmetry lex_le([D,E,F], [G,H,I]), labeling(Digits).