1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
/*-------------------------------------------------------------------------*/
/* Benchmark (Finite Domain) */
/* */
/* 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 for GNU Prolog */
/* Date : May 1993 */
/* */
/* 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:- get_fd_labeling(Lab), write('N ?'), read_integer(N),
statistics(runtime,_),
magic(N,L,Lab), statistics(runtime,[_,Y]),
write(L), nl,
write('time : '), write(Y), nl.
magic(N,L,Lab):-
fd_set_vector_max(N),
length(L,N),
fd_domain(L,0,N),
constraints(L,L,0,N,N),
lab(Lab,L).
constraints([],_,_,0,0).
constraints([X|Xs],L,I,S,S2):-
sum(L,I,X),
I1 is I+1,
S1+X#=S, % redundant constraint 1
(I=0 -> S3=S2
; I*X+S3#=S2), % redundant constraint 2
constraints(Xs,L,I1,S1,S3).
sum([],_,0).
sum([X|Xs],I,S):-
sum(Xs,I,S1),
X#=I #<=> B,
S #= B+S1.
lab(normal,L):-
fd_labeling(L).
lab(ff,L):-
fd_labelingff(L).
get_fd_labeling(Lab):-
argument_counter(C),
get_labeling1(C,Lab).
get_labeling1(1,normal).
get_labeling1(2,Lab):-
argument_value(1,Lab).
:- initialization(q).
|
