/*
From 

PRACTICAL CONSTRAINTS: A TUTORIAL ON MODELLING WITH CONSTRAINTS
ROMAN BARTÁK

http://kti.mff.cuni.cz/~bartak/NASSLLI2003/files/paper4.pdf
*/

/*
A Golomb ruler of size M is a ruler with M marks
placed in such a way that the distances between the
marks are different. The shortest ruler is optimal.

An optimal Golomb ruler of size 5 is shown below
01  4    9 11
||  |    | | 

There is no known algorithm for finding a Golomb ruler 
of size M>=24.  Design a constraint model to describe 
the problem of finding the optimal Golomb ruler.
*/


golomb(M,Sol):-
	Sol = [0|_],
	UpperBound is M*M,
	ruler(M,-1,UpperBound,Sol),
	last(Sol,XM),
	distances(Sol,1,M,XM,Dist),
	all_distinct(Dist),
	(Dist=[DF,_|_] ->
	last(Dist,DL), DF#<DL
	;
	true
	),
	minof(labeling_ff(Sol),XM).

ruler(0,_,_,[]).
ruler(K,PrevX,UpperBound,[X|Rest]):-
	K>0,
	PrevX#<X, X#=<UpperBound,
	K1 is K-1,!,
	ruler(K1,X,UpperBound,Rest).

distances([],_,_,_,[]).
distances([X|Rest],I,M,XM,Dist):-
	J is I+1,
	distances_from_x(Rest,X,I,J,M,XM,Dist,RestDist),
	I1 is I+1,!,
	distances(Rest,I1,M,XM,RestDist).

distances_from_x([],_,_,_,_,_,RestDist,RestDist).
distances_from_x([Y|Rest],X,I,J,M,XM,[DXY|Dist],RestDist):-
	DXY #= Y-X,
	LowerBound is integer(((J-I)*(J-I+1))/2),
	LowerBound #=< DXY,
	UpperBoundP is integer(((M-1-J+I)*(M-J+I))/2),
	DXY #=< XM - UpperBoundP,
	J1 is J+1,!,
	distances_from_x(Rest,X,I,J1,M,XM,Dist,RestDist).