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
114
115
116
/*
 
   
  All interval problem in Comet.
   
  CSPLib problem number 7
  http://www.cs.st-andrews.ac.uk/~ianm/CSPLib/prob/prob007/index.html
  """
  Given the twelve standard pitch-classes (c, c , d, ...), represented by
  numbers 0,1,...,11, find a series in which each pitch-class occurs exactly
  once and in which the musical intervals between neighbouring notes cover
  the full set of intervals from the minor second (1 semitone) to the major
  seventh (11 semitones). That is, for each of the intervals, there is a
  pair of neigbhouring pitch-classes in the series, between which this
  interval appears. The problem of finding such a series can be easily
  formulated as an instance of a more general arithmetic problem on Z_n,
  the set of integer residues modulo n. Given n in N, find a vector
  s = (s_1, ..., s_n), such that (i) s is a permutation of
  Z_n = {0,1,...,n-1}; and (ii) the interval vector
  v = (|s_2-s_1|, |s_3-s_2|, ... |s_n-s_{n-1}|) is a permutation of
  Z_n-{0} = {1,2,...,n-1}. A vector v satisfying these conditions is
  called an all-interval series of size n; the problem of finding such
  a series is the all-interval series problem of size n. We may also be
  interested in finding all possible series of a given size.
  """
  
  Compare with
  
 
  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/
 
/*
 
 Note: For n = 12, all 1328 solution (no symmetry breaking) took about 16
       seconds.
       With symmetry breaking: 463 solutions in 5.5 seconds.
 
 */
 
 
import cotfd;
 
int t0 = System.getCPUTime();
 
int n = 12;
int sum_distinct = ((n+1)*n) / 2;
 
Solver<CP> m();
 
var<CP>{int} x[1..n](m, 1..n);
var<CP>{int} diffs[1..n-1](m, 1..n-1);
 
 
Integer num_solutions(0);
 
exploreall<m> {
 
  forall(k in 1..n-1)
    m.post(diffs[k] == abs(x[k+1] - x[k]), onValues);
 
  m.post(alldifferent(x), onValues);
  m.post(alldifferent(diffs), onValues);
 
 
  // symmetry breaking
  m.post(x[1] < x[n-1], onValues);
  m.post(diffs[1] < diffs[2], onValues);
 
 
} using {
 
  /*
  forall(i in 1..n : !x[i].bound()) by (-x[i].getSize()) {
    // tryall<m>(v in 1..n)
    //  m.label(x[i], v);
    label(x[i]);
  }
 
  forall(i in 1..n-1 : !diffs[i].bound()) by (diffs[i].getSize()) {
    // tryall<m>(v in 1..n)
    //   m.label(x[i], v);
    label(diffs[i]);
  }
  */
 
  //label(m);
 
  label(x);
  // label(diffs);
 
 
 
 
  num_solutions := num_solutions + 1;
 
       
  cout << x << " " << sum_distinct << " " << diffs <<  endl;
  cout << flush;
 
}
 
// cout << x << 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;