Futoshiki – the code

Oh, I thought I might publish the code.  I haven’t done much in Python – but the interface to Gurobi is really nice and makes great use of list comprehensions.  I would rather use Python for mathematical programming than AMPL or OPL, as Python is a much more complete language and I can get help and extensions on the web…

#
# Futoshiki puzzle, using Gurobi
#
from gurobipy import *
# Data
dim = [1,2,3,4,5]
greater = [
  (1,1, 1,2),
  (2,3, 2,4),
  (3,2, 2,2),
  (3,3, 2,3),
  (3,4, 3,3),
  (4,3, 5,3),
  (4,5, 5,5),
  (5,2, 4,2),
  (5,3, 5,2),
  (5,3, 5,4)
  ]

try:
  # Create a new model
  m = Model("plan1")

  # Create variables
  x = {}
  for row in dim:
    for col in dim:
      x[row,col] = m.addVar(lb=1, ub=5,vtype=GRB.INTEGER, name='x_%s_%s' % (row, col))

  # Integrate new variables into the model
  m.update()

  # Relationship constraints
  for row1,col1, row2,col2 in greater:
    m.addConstr(x[row1,col1] >= 1 + x[row2,col2], 'gt_%s_%s_%s_%s' % (row1,col1,row2,col2))

  # Each digit appears only once per row
  for i in dim:
    m.addConstr(quicksum(x[i,col] for col in dim) == 15, 'row_%s' % (i))
    m.addConstr(quicksum(x[row,i] for row in dim) == 15, 'col_%s' % (i))
  m.addConstr(quicksum(x[i,j] for i,j in x) == 15*5, 'total')

  # Solve it
  m.optimize()

  # Display the solution
  for v in m.getVars():
    print v.varName, v.x

  print 'Obj:', m.objVal

except GurobiError:
  print 'Error reported'