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 | %-----------------------------------------------------------------------------% % Golomb rulers % prob006 in csplib %-----------------------------------------------------------------------------% % From csplib: % A Golomb ruler may be defined as a set of m integers 0 = a_1 < a_2 < % ... < a_m such that the m(m-1)/2 differences a_j - a_i, 1 <= i < j % <= m are distinct. Such a ruler is said to contain m marks and is of % length a_m. The objective is to find optimal (minimum length) or % near optimal rulers. % % This is the "ternary constraints and an alldifferent" model %-----------------------------------------------------------------------------% include "globals.mzn" ; int : m; int : n = m * m; array [1 .. m] of var 0 .. n: mark; array [1..(m*(m - 1)) div 2] of var 0 .. n: differences = [ mark[j] - mark[i] | i in 1 .. m, j in i + 1 .. m]; constraint mark[1] = 0; constraint forall ( i in 1 .. m - 1 ) ( mark[i] < mark[i + 1] ); constraint alldifferent(differences); % Symmetry breaking constraint differences[1] < differences[(m*(m - 1)) div 2]; solve :: int_search(mark, input_order, indomain, complete) minimize mark[m]; output [ show (mark)]; %-----------------------------------------------------------------------------% %-----------------------------------------------------------------------------% |