Iain Dunning

Experiences, thoughts, and technical notes. More about me. @iaindunning

Solving a Combination Lock Puzzle with JuMP + Julia

Posted on 21 Sep 2013

The PuzzlOR is a website connected to INFORMS that publishes operations research-related problems bimonthly. In a series of posts I'm going to solve some of the problems to demonstrate JuMP, an algebraic modeling language for/in Julia.

Combination Locks (August 2012)

(Link to full problem statement)

Our goal is to determine 6 numbers, where each of the 6 numbers has 6 possibilities and the sum of the numbers is 419. Lets first describe the possibilities (pulled from the image) as a matrix P:

$$ P = \begin{bmatrix} 39 & 06 & 75 & 88 & 15 & 57 \\ 9 & 2 & 58 & 68 & 48 & 64 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 44 & 63 & 10 & 83 & 46 & 03 \end{bmatrix} $$

We will model the problem as a integer program with variables \( x_{ij} \) that equal 1 if and only if for lock (row) i we select the number (column) j. Our model is thus the following feasibility problem:

$$ \begin{alignat*}{1} \max \quad & 0\\ \text{subject to} \quad & \sum_{ij}D_{ij}x_{ij}=419\\ & \sum_{j=1}^6 x_{ij} = 1 \qquad \forall i \in \{1,\dots,6\}\\ & x_{ij}\in\left\{ 0,1\right\} \end{alignat*} $$

where the first constraint enforces the sum of the numbers equals 419, and the second constraint ensures we pick a number for each lock. We can solve this problem with the following code:

# Assuming a solver has been previously installed, e.g. Cbc
using JuMP

function SolveCombination(P)
  m = Model()
  
  # Variable x: 1 iff select number j for lock i
  @defVar(m, 0 <= x[i=1:6, j=1:6] <= 1, Int)

  # Constraint 1: Sum of numbers is equal to 419
  @addConstraint(m, sum{P[i,j]*x[i,j], i=1:6, j=1:6} == 419)

  # Constraint 2: Must pick a number from each lock
  for i in 1:6
    @addConstraint(m, sum{x[i,j], j=1:6} == 1)
  end

  # Solve with default solver (CBC)
  status = solve(m)

  if status == :Infeasible
    println("Couldn't find the numbers!")
  else
    println("Found the numbers:")
    for i in 1:6
      for j in 1:6
        if getValue(x[i,j]) >= 0.99
          println("Lock $i is $(P[i,j])")
          break
        end
      end
    end
  end
end

P = [39 06 75 88 15 57;
      9  2 58 68 48 64;
     29 55 16 67  8 91;
     40 54 66 22 32 25;
     49  1 17 41 14 30;
     44 63 10 83 46  3]
SolveCombination(P)


An extension question: what happens if relax constraint 2? How many locks would we need to make the sum 419 if we didn't need to set all 6 locks?



© 2013 Iain Dunning
Contact me by email (idunning AT mit DOT edu), @iaindunning, LinkedIn, GitHub
This website was made with Jekyll and Skeleton.