## Tuesday, 22 November 2016

### Constraint Programming with python-constraint

I have recently been looking at constraint programming and I thought I would post some of my code as I go. This is using the python-constraint package.

Doing things with python-constraint is pretty easy. To constrain a variable to have a certain value, we can use InSetConstraint. To make sure all the variables in a set are different, we use the AllDifferentConstraint. These are enough to solve sudoku.

# Sudoku

I don't think Sudoku needs any introduction. The constraints are fairly easy to specify: each row must be all different, each col must be all different and each 3x3 block must be all different. Also we have to ensure that the given starting state is used, for this we use equality constraints. We use 1 variable for each number in the sudoku square, so 81 variables all up.

`from constraint import *problem = Problem()problem.addVariables(range(9*9), range(1,10))# specify the given starting sudoku problem here, dots are blank squaressudoku = '\.42986.1.\....2...5\......82.\4.1..793.\.683.254.\.758..1.2\.39......\7...4....\.1.67325.'# Make sure our solution matches the specified starting thingfor i,char in enumerate(sudoku):    if char != '.':  problem.addConstraint(InSetConstraint([int(char)]),[i])    # add row and col constraintsfor i in range(9):     problem.addConstraint(AllDifferentConstraint(),range(9*i,9*i+9))for i in range(9):     problem.addConstraint(AllDifferentConstraint(),range(i,81,9))# add block constraintsfor i in [0,3,6,27,30,33,54,57,60]:     ind = []    for j in range(3):        for k in range(3):            ind.append(i + j*9 + k)    problem.addConstraint(AllDifferentConstraint(),ind)# pretty print the outputa = problem.getSolution()for i in range(9):    for j in range(9): print a[i*9+j],    print ''`

# The Golomb Ruler

A bit of info on Golomb Rulers: here. If you know how to improve the code below, leave a comment. Golomb rulers are described by their order, which is the number of marks on their edge. The length of a Golomb ruler is the distance between the outer two marks and represents the longest distance it can measure.

There is no requirement that a Golomb ruler measures all distances up to their length. However, if a ruler does measure all distances, it is classified as a perfect Golomb ruler. There are no perfect Golomb rulers above order 4.

Finally, a Golomb ruler is described as optimal if no shorter ruler of the same order exists. The code below first looks for perfect rulers, then increments length each time until an optimal ruler is found. It starts to slow down by order = 7, it takes a few minutes.

This problem is harder than the sudoku problem, we have to use a set of auxiliary variables to represent the pairwise differences, then apply the AllDifferentConstraint to the auxiliary variables.

`from constraint import *from itertools import combinationsorder = 7 # the number of marks on the Golomb rulerdiffs = [] # the set of pairwise differences between marksfor i in combinations(range(order),2): diffs.append(i)length = len(diffs)def lessthan(a,b): return a < bdef diffeq(a,b,res): return (b-a)==res     while True:    print 'trying length: '+str(length)    problem = Problem()    problem.addVariables(range(order), range(0,length+1))    problem.addVariables(diffs,    range(1,length+1))    # make sure the first mark is 0 and last is length    problem.addConstraint(InSetConstraint([0]),[0])    problem.addConstraint(InSetConstraint([length]),[order-1])    # ensure that the marks are in increasing order    # make sure all possible pairwise relations are constrained    for i in diffs: problem.addConstraint(lessthan,[i[0],i[1]])    # ensure that the differences reflect the marks    for i in diffs: problem.addConstraint(diffeq,[i[0],i[1],i])        # all the differences must be different        problem.addConstraint(AllDifferentConstraint(),diffs)       # pretty print the output    solutions = problem.getSolutions()    for ruler in solutions:        for mark in range(order): print ruler[mark],        print ''    if len(solutions) > 0: break # if we find some solutions, quit    length = length + 1`

example output for order = 7, note the shortest ruler is length 25, though a perfect ruler would be length 21:

`trying length: 21trying length: 22trying length: 23trying length: 24trying length: 250 4 9 15 22 23 250 3 4 12 18 23 250 2 3 10 16 21 250 2 5 14 18 24 250 2 6 9 14 24 250 2 7 13 21 22 250 2 7 15 21 24 250 1 4 10 18 23 250 1 7 11 20 23 250 1 11 16 19 23 25`

# Magic Squares

Magic Squares seem to be very common examples when doing constraint programming, so I may as well include the code for them. Info on Magic Squares can be found here. This code is quite slow, I thought it would be much faster. This may be because python-constraint is just kind of slow, or maybe the problem is harder than I thought.

`from constraint import *problem = Problem()size = 4problem.addVariables(range(size*size), range(1,size*size+1))total = size*(size*size + 1)/2# make sure rows add to totalfor i in range(size):     problem.addConstraint(ExactSumConstraint(total),range(i*size,i*size+size))for i in range(size):     problem.addConstraint(ExactSumConstraint(total),range(i,size*size,size))# add the diagonal constraintsdiag1,diag2 = [],[]for i in range(size):    diag1.append(i*size + i)    diag2.append(i*size + (size-i-1))problem.addConstraint(ExactSumConstraint(total),diag1)problem.addConstraint(ExactSumConstraint(total),diag2)problem.addConstraint(AllDifferentConstraint())   # pretty print the outputsolution = problem.getSolution()for i in range(size):    for j in range(size):        print solution[i*size + j],    print ''`