/*-------------------------------------------------------------------------*/
/* Benchmark (Finite Domain)            INRIA Rocquencourt - ChLoE Project */
/*                                                                         */
/* Name           : magic.pl                                               */
/* Title          : magic series                                           */
/* Original Source: W.J. Older and F. Benhamou - Programming in CLP(BNR)   */
/*                  (in Position Papers of PPCP'93)                        */
/* Adapted by     : Daniel Diaz - INRIA France                             */
/* Date           : May 1993                                               */
/* Adapted for ECLIPSE by Antonio FErnandez                                */
/* Date :     21 April                                                     */
/* Readated for Gnu Prolog by Hector Palacios                              */
/* Date:      Mar 07 2001.                                                 */
/*                                                                         */
/* A magic serie is a sequence x0, x1, ..., xN-1 such that each xi is the  */
/* number of occurences of i in the serie.                                 */
/*           N-1                                                           */
/*  ie  xi = Sum (xj=i)  where (xj=i) is 1 if x=y and 0 if x<>y            */
/*           i=0                                                           */
/*                                                                         */
/* two redundant constraints are used:                                     */
/*           N-1                     N-1                                   */
/*           Sum i = N          and  Sum i*xi = N                          */
/*           i=0                     i=0                                   */
/*                                                                         */
/* Note: in the Pascal's original version the length of a magic serie is   */
/* N+1 (x0, x1, ..., XN) instead of N (x0, x1, ..., xN-1). Finding such a  */
/* serie (for N) only corresponds to find a serie for N+1 in this version. */
/* Also the original version only used one redundant constraint.           */
/*                                                                         */
/* Solution:                                                               */
/* N=1,2,3 and 6 none                                                      */
/* N=4  [1,2,1,0] and [2,0,2,0]                                            */
/* N=5  [2,1,2,0,0]                                                        */
/* N=7  [3,2,1,1,0,0,0]   (for N>=7  [N-4,2,1,<N-7 0's>,1,0,0,0])          */
/*-------------------------------------------------------------------------*/


q:-     write('N? '), read(N),
        statistics(runtime,_),magic(N,L),
        statistics(runtime,[_,Y]),
        write(L), nl,
        write('time : '), write(Y), nl.

magic2(N, L):-
	get_list(N, L),
	fd_domain(L, 0, N),
	fd_labelingff(L).


magic(N, L):-
	get_list(N, L),
	N1 is N-1,
	fd_domain(L, 0, N1),
	constraints(L, L, 0, N, N),
	fd_labelingff(L).


get_list(0, L) :- !,
	L=[].
get_list(M, L) :-
	L = [_|L0],
	M1 is M-1,
	get_list(M1, L0).

constraints([], _, _, S0, S1) :- S0=0, S1=0.
constraints([X|Xs], L, I, S, S2):-
    	sum(L, I, X),
	I1 is I+1,
	S1 #>= 0,
	%S1+X #= S,				% redundant constraint 1
	c_0(I, X, S2, S3),
	constraints(Xs, L, I1, S1, S3).

c_0(0, _X, S0, S1) :- !, S0=S1.
c_0(I, X, S0, S1) :- I*X+S1#=S0.


sum([], _, 0).
sum([X|Xs], I, S) :-
        fd_domain(B, 0, 1),
        X#=I #<=>B,
	S#=B+S1,
	sum(Xs, I, S1).