1# --------------------------------------------------------------------------
2# Source file provided under Apache License, Version 2.0, January 2004,
3# http://www.apache.org/licenses/
4# (c) Copyright IBM Corp. 2015, 2022
5# --------------------------------------------------------------------------
6
7"""
8In mathematics, a Golomb ruler is a set of marks at integer positions along
9an imaginary ruler such that no two pairs of marks are the same distance apart.
10The number of marks on the ruler is its order, and the largest distance
11between two of its marks is its length.
12
13See https://en.wikipedia.org/wiki/Golomb_ruler for more information.
14
15For order 5: 2 solutions 0 1 4 9 11 ; 0 2 7 8 11
16
17Please refer to documentation for appropriate setup of solving configuration.
18"""
19
20from docplex.cp.model import CpoModel
21from sys import stdout
22
23
24#-----------------------------------------------------------------------------
25# Initialize the problem data
26#-----------------------------------------------------------------------------
27
28# Number of marks on the ruler
29ORDER = 8
30
31
32#-----------------------------------------------------------------------------
33# Prepare the data for modeling
34#-----------------------------------------------------------------------------
35
36# Estimate an upper bound to the ruler length
37MAX_LENGTH = (ORDER - 1) ** 2
38
39
40#-----------------------------------------------------------------------------
41# Build the model
42#-----------------------------------------------------------------------------
43
44# Create model
45mdl = CpoModel()
46
47# Create array of variables corresponding to position ruler marks
48marks = mdl.integer_var_list(ORDER, 0, MAX_LENGTH, "M")
49
50# Create marks distances that should be all different
51dist = [marks[i] - marks[j] for i in range(1, ORDER) for j in range(0, i)]
52mdl.add(mdl.all_diff(dist))
53
54# Avoid symmetric solutions by ordering marks
55mdl.add(marks[0] == 0)
56for i in range(1, ORDER):
57 mdl.add(marks[i] > marks[i - 1])
58
59# Avoid mirror solution
60mdl.add((marks[1] - marks[0]) < (marks[ORDER - 1] - marks[ORDER - 2]))
61
62# Minimize ruler size (position of the last mark)
63mdl.add(mdl.minimize(marks[ORDER - 1]))
64
65
66#-----------------------------------------------------------------------------
67# Solve the model and display the result
68#-----------------------------------------------------------------------------
69
70print("\nSolving model....")
71msol = mdl.solve(TimeLimit=100)
72
73# Print solution
74if msol:
75 stdout.write("Solution: " + msol.get_solve_status() + "\n")
76 stdout.write("Position of ruler marks: ")
77 for v in marks:
78 stdout.write(" " + str(msol[v]))
79 stdout.write("\n")
80 stdout.write("Solve time: " + str(round(msol.get_solve_time(), 2)) + "s\n")
81else:
82 stdout.write("Search status: " + msol.get_solve_status() + "\n")