Golomb Ruler

This is an example showing how to solve the Golomb ruler problem using numberjack.

Description: 

The Golomb Ruler problem is the task of putting n marks on a ruler of length m such that the distance between any two pairs of marks is distinct. See prob006 in the CSPLib.

Code: 

from Numberjack import *

def model_golomb_ruler(nbMarks):
    rulerSize = 2**(nbMarks-1)

    marks = VarArray(nbMarks,rulerSize)
    model = Model(
        Minimise( marks[nbMarks-1] ), #objective function

        [marks[i-1] < marks[i] for i in range(1,nbMarks)],
        AllDiff([marks[i] - marks[j] for i in range(1, nbMarks) for j in range(i)]),
        marks[0] == 0 # symmetry breaking
        )
    return (marks,model)

def solve_golomb_ruler(param):
    (marks,model) = model_golomb_ruler(param['marks'])
    solver = model.load(param['solver'])
    solver.solve()
    print marks
    print 'Nodes:', solver.getNodes(), ' Time:', solver.getTime()

solve_golomb_ruler(input({'solver':'Mistral','marks':6}))