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 | % % 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. % % Currently (1999), optimal rulers are known up to n=21. % % ECLiPSe solution by Joachim Schimpf, IC-Parc. The code is inspired % by Jean-Francois Puget and Michel Leconte's ILOG solver solution. % % N Opt Backtr Backtr Time(s) % to opt total total % 5 11 0 0 0.0 % 6 17 0 3 0.0 % 7 25 7 24 0.4 % 8 34 45 186 3.8 % 9 44 309 1013 33.4 % 10 55 2797 6008 287 % 11 72 15597 88764 6500 % 12 85 487865 763328 75300 % :- lib(ic). :- lib(ic_global). :- lib(branch_and_bound). :- import alldifferent/1 from ic_global. golomb( N , Xs ) :- length( Xs , N ), % model NN is 2^( N -1)-1, Xs :: [0.. NN ], once append([0| _ ], [ Xn ], Xs ), ordered(<, Xs ), distances( Xs , Diffs ), Diffs ::[1.. NN ], alldifferent( Diffs ), once append([ D1 | _ ], [ Dn ], Diffs ), D1 #< Dn , bb_min (labeling( Xs ), Xn , _default ). % search distances([], []). distances([ X | Ys ], D0 ) :- distances( X , Ys , D0 , D1 ), distances( Ys , D1 ). distances( _ , [], D , D ). distances( X , [ Y | Ys ], [ Diff | D1 ], D0 ) :- Diff #= Y - X , distances( X , Ys , D1 , D0 ). |