/*-------------------------------------------------------------------------*/
/* 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                                              */
/*                                                                         */
/* 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])         */
/*-------------------------------------------------------------------------*/

:- lib(fd). 

:- dynamic magic/2.
:- dynamic constraints/6.
:- dynamic summe/3.     
:- dynamic adk/3.
:- dynamic user_labeling/3.

magic(N,L):-
        length(L,N),
        L :: 0..N, 
	V_N :: N..N,
        constraints(L,L,0,V_N,V_N,N), write('userlab'),nl,
        user_labeling(L,1,L).


constraints([],_,_,V1,V2,_):-
	V1 #= 0,
	V2 #= 0.

% constraints(+FdVar List, +FdVar List, +Int, FdVar, +FdVar, +Int)
constraints([X|Xs],L,I,S,S2,N):-
        summe(L,I,NbIinL),
	X #= NbIinL,
	S1 :: 0..N,
        S1 + X #= S,                       % contrainte redondante 1
	S3 :: 0..N,
        (I=0 -> S3#=S2
             ;  (  Z :: 0..N, V_I :: I..I, V_I*X #= Z, Z+S3#=S2)),     % contrainte redondante 2 X * Y #= Z
        I1 is I+1,
        constraints(Xs,L,I1,S1,S3,N).

% summe(+FdVar List, -Int)
summe([],_,0).

summe([X|Xs],I,S):-
        summe(Xs,I,S1),
        adk(X,I,B),
        S is S1+B.

% adk(+FdVar, +Int, -Int)
adk(X,I,0) :- X ## I.
adk(X,I,1) :- X #= I.


user_labeling([],_,_).
user_labeling([X | L],N,L0) :-
        indomain(X),
	N1 is N+1,
        user_labeling(L,N1,L0).

/*
user_labeling([],_,_).
user_labeling([X | L],N,L0) :-
        dvar_domain(X,D), dom_range(D,Min,Max), X #= Min, N1 is N+1,
        user_labeling(L,N1,L0).
user_labeling([X | L],N,L0) :-
        dvar_domain(X,D), dom_range(D,Min,Max), X #> Min,
        user_labeling([X | L], N, L0).                                                                       
*/