%
% 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).