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 | /* Golomb ruler in B-Prolog. 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. Model created by Hakan Kjellerstrand, hakank@gmail.com*/% Licenced under CC-BY-4.0 : http://creativecommons.org/licenses/by/4.0/go :- time2(golomb(8, Xs)), writeln(Xs).time2(Goal):- cputime(Start), statistics(backtracks, Backtracks1), call(Goal), statistics(backtracks, Backtracks2), cputime(End), T is (End-Start)/1000, Backtracks is Backtracks2 - Backtracks1, format('CPU time ~w seconds. Backtracks: ~d\n', [T, Backtracks]).golomb(N, Xs) :- writeln('N':N), length(Xs, N),% model NN is 2**(N-1)-1, Xs :: 0..NN, Xn #= Xs[N], % to minimize alldifferent(Xs), increasing(Xs), Xs[1] #= 0, Diffs @= [Diff : I in 1..N, J in 1..N, [Diff], (I \= J, Diff #= Xs[I]-Xs[J])], alldifferent(Diffs), % Symmetry breaking Diffs[1] #< Diffs[N], Xs[2] - Xs[1] #< Xs[N] - Xs[N-1], term_variables([Diffs,Xs], Vars), minof(labeling([ff,down],Vars), Xn, format("Xn: ~d\n",[Xn])).increasing(List) :- Len @= List^length, foreach(I in 2..Len, List[I-1] #< List[I]). |