%
% All interval problem in ASP.
%
% 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.
% """
%
% This was created by Hakan Kjellerstrand, hakank@bonetmail.com
% See also http://www.hakank.org/answer_set_programming/
%
#const n = 11.
% indices
ix(1..n).
diffs_ix(1..n-1).
values(1..n).
diffs_values(1..n-1).
% unique index for diffs
1 { diffs(I, Val) : diffs_values(Val) } 1 :- diffs_ix(I).
% alldifferent for diffs
1 { diffs(I, Val) : diffs_ix(I) } 1 :- diffs_values(Val).
% unique index for x
1 { x(I, Val) : values(Val) } 1 :- ix(I).
% alldifferent for x
1 { x(I, Val) : ix(I) } 1 :- values(Val).
diffs(K, S) :- S = #abs(Val1-Val), x(K+1, Val1), x(K,Val), diffs_ix(K).
% symmetry breaking
% x[1] < x[n-1]
:- x(1,Val1), x(n-1, Val2), Val1 >= Val2.
% diffs[1] < diffs[2]
:- diffs(1, Val1), diffs(2, Val2), Val1 >= Val2.
#hide.
#show x(I,Val).
#show diffs(I, Val).