Download
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/*
 
  Magic sequence in Comet.
 
  From CSPLib problem 19:
  """
  A magic sequence of length n is a sequence of integers x0 . . xn-1 between
  0 and n-1, such that for all i in 0 to n-1, the number i occurs exactly
  xi times in the sequence. For instance, 6,2,1,0,0,0,1,0,0,0 is a magic
  sequence since 0 occurs 6 times in it, 1 occurs twice, ...
  """
 
  This model is not very unlike the OPL models magic1.mod, magic2.mod,
  and magic3.mod in
  Pascal Van Hentenryck "The OPL Optimization Programming Language", page 39ff.
 
 
  The problem n = 50 is solved in about 1 second, n = 500 is solved in about 18 seconds.
 
 
  This Comet model was created by Hakan Kjellerstrand (hakank@gmail.com)
  Also, see my Comet page: http://www.hakank.org/comet
 
 */
 
// Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/
 
import cotfd;
 
int t0 = System.getCPUTime();
 
int n = 50;
range Range = 0..n-1;
range Domain = 0..n;
 
int value[i in Range] = i;
 
Solver<CP> m();
var<CP>{int} s[Range](m, Domain);
 
Integer num_solutions(0);
 
 
//
// distribute
//
// Imitates the OPL constraint distribute.
//
class distribute extends UserConstraint<CP> {
  var<CP>{int}[] _occurrence;
  int[] _value;
  var<CP>{int}[] _element;
  int _n;
   
  distribute(var<CP>{int}[] occurrence,
             int[] value,
             var<CP>{int}[] element) : UserConstraint<CP>() {
    _occurrence = occurrence;
    _value = value;
    _element = element;
    _n = _occurrence.getSize();     
  }
 
  Outcome<CP> post(Consistency<CP> cl) {
    Solver<CP> cp = _occurrence[1].getSolver();
    range Range = _occurrence.getRange();
    forall(i in Range)
      cp.post(sum(j in Range) (_occurrence[j] == _value[i]) == _element[i]);
 
    return Suspend;
  }
 
  Outcome<CP> propagate() {
    return Suspend;
  }
 
}
 
 
explore<m> {
 
  /*
  // original constraint
  forall(i in Range)
    m.post(s[i] == sum(j in Range) (s[j] == i));
  */
 
  // added in the OPL model magic2.mod
  m.post(sum(i in Range) s[i] == n);
  m.post(sum(i in Range) s[i]*i == n);
 
  // added in the OPL model magic3.mod
  m.post(distribute(s, value, s));
 
} using {
       
  labelFF(m);
 
  num_solutions++;
       
  cout << s << endl;
 
}
 
 
cout << "\nnum_solutions: " << num_solutions << endl;
     
int t1 = System.getCPUTime();
cout << "time:      " << (t1-t0) << endl;
cout << "#choices = " << m.getNChoice() << endl;
cout << "#fail    = " << m.getNFail() << endl;
cout << "#propag  = " << m.getNPropag() << endl;