c:\george>bp
B-Prolog Version 7.1b1, All rights reserved, (C) Afany Software
1994-2007.
Licensed for educational and nonprofit research uses only.
| ?- cl(golomb)
Compiling::golomb.pl
compiled in 16 milliseconds
loading::golomb.out
yes
| ?- go
[0,2,5,25,37,43,59,70,85,89,98,99,106]
time(-217433257)
A solution to the golomb 13 problem was found over the weekend
(obviously the time integer overflowed) on my PC (Pentium 4, 3GHz,
1GRAM). Is this the largest problem instance that has been solved by
CLP(FD)? In the tutorial, solutions are given to instances up to size
12.
go:-
cputime(Start),
golomb(13,Sol),
cputime(End),
T is End-Start,
writeln(Sol),
writeln(time(T)).
/*
Taken from PRACTICAL CONSTRAINTS: A TUTORIAL ON MODELLING WITH
CONSTRAINTS,
by ROMAN BART=81=C1K
*/
golomb(M,Sol):-
Sol =3D [0|_],
UpperBound is M*M,
ruler(M,-1,UpperBound,Sol),
last(Sol,XM),
distances(Sol,1,M,XM,Dist),
all_distinct(Dist),
(Dist=3D[DF,_|_] ->
last(Dist,DL), DF#<DL
;
true
),
minimize(labeling([ff],Sol),XM).
ruler(0,_,_,[]).
ruler(K,PrevX,UpperBound,[X|Rest]):-
K>0,
PrevX#<X, X#=3D<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 #=3D Y-X,
LowerBound is integer(((J-I)*(J-I+1))/2),
LowerBound #=3D< DXY,
UpperBoundP is integer(((M-1-J+I)*(M-J+I))/2),
DXY #=3D< XM - UpperBoundP,
J1 is J+1,!,
distances_from_x(Rest,X,I,J1,M,XM,Dist,RestDist).
last([X],X):-!.
last([_|Xs],X):-last(Xs,X).
minimize(Choice,Exp):-minof(Choice,Exp).
|
