A golomb ruler is an assignment of marks to integer positions along a ruler so that no pair of two marks is the same distance from each other. The number of marks is the order of the ruler. The first mark is required to be at position 0, the position of the highest mark is the length of the ruler. The problem is finding the shortest ruler of a given order.
Input
-----
A number of marks, given as a range of consecutive, ascending integers, starting at 1.
A number of positions, given as a range of consecutive, ascending integers, starting at 0.
For example:
mark(1). mark(2). position(0). position(1). position(2). position(3). position(4).
Output
------
A location fact for each mark giving its position on the ruler. The optimisation criteria is the length of the ruler. Continuing the above example:
location(1,0). location(2,1).
is the optimal solution, with a length of 1.
Calibration
-----------
Calibration was performed on a 1.8 Ghz Pentium M using GrinGo 2.0.2 and Clasp 1.1.3.
Suggested competition set - 9/75, 10/75, 11/100, 12/100, 13/125, 14/150
Optimal values are:
8 34
9 44
10 55
11 72
12 85
13 106
14 127
15 151