Langford's number

This is an example of solving the Langford's number problem with Numberjack.


Consider two sets of the numbers from 1 to 4. The problem is to arrange the eight numbers in the two sets into a single sequence in which the two 1's appear one number apart, the two 2's appear two numbers apart, the two 3's appear three numbers apart, and the two 4's appear four numbers apart.

The problem generalizes to the L(k,n) problem, which is to arrange k sets of numbers 1 to n, so that each appearance of the number m is m numbers on from the last. For example, the L(3,9) problem is to arrange 3 sets of the numbers 1 to 9 so that the first two 1's and the second two 1's appear one number apart, the first two 2's and the second two 2's appear two numbers apart, etc. See prob024 in the CSPLib.


from Numberjack import *

def model_langford_sequence(M,N):
    X = [Variable(1, N*M-(i+2)*(M-1)) for i in range(N)]
    model = Model(
        AllDiff( [X[i]+((i+2)*j) for j in range(M) for i in range(N)] ),
        X[0] > X[1] # Break symmetry
    return (X,model)

def compute_langford_number(param):
    (X,model) = model_langford_sequence(param['M'],param['N'])
    solver = model.load(param['solver'])
    langford_number = 0
    while solver.getNextSolution() == SAT:
        langford_number += 1
    print 'L('+str(param['M'])+','+str(param['N'])+') =', langford_number
    print 'Nodes:', solver.getNodes(), ' Time:', solver.getTime()

def printLangford(M,X):
    N = len(X)
    sequence = [0]*(M*N)
    for i in range(N):
        for j in range(M):
            sequence[X[i].get_value()+j*(i+2)-1] = (i+1)
    print sequence

compute_langford_number(input({'solver':'Mistral', 'N':10, 'M':3}))