006: Golomb rulers

/*

  Golomb ruler in Picat.

  A Golomb ruler is a set of integers (marks) a(1) < ...  < a(n) such
  that all the differences a(i)-a(j) (i > j) are distinct.  Clearly we
  may assume a(1)=0.  Then a(n) is the length of the Golomb ruler.
  For a given number of marks, n, we are interested in finding the
  shortest Golomb rulers.  Such rulers are called optimal. 

  See http://www.research.ibm.com/people/s/shearer/grule.html


  Model created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

% Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/

import util.
import cp.


main => go.

go =>
        time2($golomb(8, Xs)),
        writeln(Xs).


golomb(N, Xs) =>

        writeln(n=N),
        Xs = new_list(N),
        NN = 2**(N-1)-1,
        Xs :: 0..NN,
        Xn #= Xs[N], % to minimize

        all_different(Xs),
        increasing(Xs),
        Xs[1] #= 0,

        Diffs = [Diff : I in 1..N, J in 1..N, 
                 I != J, Diff #= Xs[I]-Xs[J]],
        all_different(Diffs),

        % Symmetry breaking
        Diffs[1] #< Diffs[N],
        Xs[2] - Xs[1] #< Xs[N] - Xs[N-1],

        Vars = Diffs ++ Xs,
        solve([$min(Xn),ff,down],Vars).

increasing(List) =>
   foreach(I in 2..List.length) List[I-1] #=< List[I] end.