006: Golomb rulers

/*
 * SICSTUS CLPFD DEMONSTRATION PROGRAM
 * Purpose   : Golomb Ruler
 * Author    : Mats Carlsson
 *
 * | ?- golomb([], 12, bound).
 */

:- module(golomb, [
	golomb/3
	]).
:- use_module(library(lists), [
	last/2
	]).
:- use_module(library(clpfd)).

%
% compute an optimum golomb ruler with N marks
%
golomb(Lab, N, Consistency) :-
	marks(N, Marks, Last, [consistency(Consistency)]),
	indomain(Last),
	labeling(Lab, Marks),
	writeq(Marks),
	nl.

marks(N1, [0|Xs], Xn, Opt) :-
	N is N1-1,
	length(Xs, N),
	Max is N*N,
	domain(Xs, 1, Max),
	deltas(Xs, Triangle, Opt, Ds, Xs),
	(   foreach(Row,[Xs|Triangle])
	do  (   foreach(D,Row),
		count(J,1,_)
	    do  d(J, N2),
		D #>= N2
	    )
	),
	Xs = [X1|_],
	last(Xs, Xn),
	last(Triangle, [Dmn]),
	X1 #< Dmn,		% break symmetries
	all_distinct(Ds, Opt).

deltas([_], [], _Opt) --> !.
deltas([X|Xs], [Row|Triangle], Opt) -->
	(   foreach(Xj,Xs),
	    foreach(Dij,Row),
	    param([X,Opt])
	do  [Dij],
	    {scalar_product([1,-1], [Xj,X], #=, Dij, Opt)}
	),
	deltas(Xs, Triangle, Opt).

d( 1,  1).
d( 2,  3).
d( 3,  6).
d( 4,  11).
d( 5,  17).
d( 6,  25).
d( 7,  34).
d( 8,  44).
d( 9,  55).
d(10,  72).
d(11,  85).
d(12, 106).
d(13, 127).
d(14, 151).
d(15, 177).
d(16, 199).
d(17, 216).
d(18, 246).
d(19, 283).
d(20, 333).
d(21, 356).
d(22, 372).
d(23, 425).