/*-------------------------------------------------------------------------*/
/* Nom             : magic.pl                                              */
/* Titre           : magic series                                          */
/* Source originale: W.J. Older and F. Benhamou - Programming in CLP(BNR)  */
/*                   (in Position Papers of PPCP'93)                       */
/* Adapte par      : Daniel Diaz - INRIA France                            */
/* Date            : Mai 1993                                              */
/* Adapte par      : Pierre Deransart - INRIA France                       */
/* Date            : Mars 2002                                             */
/*                                                                         */
/* Une suite ``magique'' est une sequence x0, x1, ..., xN-1 telle que      */
/* chaque xi est le nombre d'occurrences de i dans la sequence             */
/*           N-1                                                           */
/*  ie  xi = Som (xj=i)  oł  (xj=i) vaut 1 si x=y et  0 si  x<>y           */
/*           j=0                                                           */
/*                                                                         */
/* Le programme utilise deux contraintes redondantes:                      */
/*           N-1                     N-1                                   */
/*           Som i = N          and  Som i*xi = N                          */
/*           i=0                     i=0                                   */
/*                                                                         */
/* Solutions:                                                              */
/* N=0  []                                                                 */
/* N=1,2,3 et  6 aucune                                                    */
/* N=4  [1,2,1,0] et  [2,0,2,0]                                            */
/* N=5  [2,1,2,0,0]                                                        */
/* N=7  [3,2,1,1,0,0,0]   (pour N>=7  [N-4,2,1,<N-7 0's>,1,0,0,0])         */
/*-------------------------------------------------------------------------*/

:- dynamic magic/2.
:- dynamic sumcr/5.
:- dynamic constraints/4.
:- dynamic nbI/4.
:- dynamic adk/3.

magic(N,L):-
        length(L,N),
        L :: 0..N,
	V_N :: N..N,
        sumcr(L, 0, V_N, V_N, N),
        constraints(L, 0, L, N).

% sumcr(FdVar List, Int, FdVar, FdVar, Int)
sumcr([],_,V1,V2, _):-
	V1 #= 0,
	V2 #= 0.

sumcr([X|Xs],I,S,S2, N):-
	%S1 :: 0..N,
        %S1+X#=S,                                % contrainte redondante 1
        (I=0 -> S3=S2
             ;  S3 :: 0..N,
	        V_I :: I..I, Z :: 0..N,  V_I*X #= Z, Z+S3#=S2),
	        %I*X+S3#=S2),                    % contrainte redondante 2
        I1 is I+1,
        %sumcr(Xs, I1, S1, S3, N),
        sumcr(Xs, I1, S, S3, N).

constraints([], _ , _, _N).

constraints([X|Xs], I, L, N):-
        nbI(L, I, X, N),
        I1 is I+1,
        constraints(Xs, I1, L, N).

% sum(FdVar List, Int, FdVar, Int)
nbI([], _I, Zero, _N):-
	Zero #= 0.
nbI([X|R], I, NbIinXR, N):-
	adk(X, I, B),

	length(R, LenR),
	NbIinR :: 0..LenR,
	nbI(R, I, NbIinR, N),

	NbIinXR #= NbIinR + B.

adk(X,I, 0) :- X ## I.
adk(X,I, 1) :- X #= I.