PuzzlOR: Combination Locks

The Combination Locks Puzzle¶

http://puzzlor.com/2012-08_CombinationLocks.html

In [5]:

using JuMP
m = Model()

Out[5]:

$$ \begin{alignat*}{1}\min\quad & 0\\ \text{Subject to} \quad\end{alignat*} $$

In [6]:

# x is a binary variable
# x_i,j = 1   If the i_th number on the j_th lock is selected
# x_i,j = 0   Otherwise
@defVar(m, x[i=1:6,j=1:6], Bin)

Out[6]:

$$ x_{i,j} \in \{0,1\} \quad\forall i \in \{1,2,\dots,5,6\}, j \in \{1,2,\dots,5,6\} $$

In [7]:

# Model Data
LockNumbers = [ 39  6 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]

Out[7]:

6x6 Array{Int32,2}:
 39   6  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

In [9]:

# Constraints 1-6: only 1 number selected for each lock
for i = 1:6
    @addConstraint(m, sum{x[i,j], j=1:6} == 1)
end

In [11]:

# Constraint 7: Lock numbers sum to 419
@addConstraint(m, sum{LockNumbers[i,j]*x[i,j], i=1:6, j=1:6} == 419)

Out[11]:

$$ 39 x_{1,1} + 6 x_{1,2} + 75 x_{1,3} + 88 x_{1,4} + 15 x_{1,5} + 57 x_{1,6} + 9 x_{2,1} + 2 x_{2,2} + 58 x_{2,3} + 68 x_{2,4} + 48 x_{2,5} + 64 x_{2,6} + 29 x_{3,1} + 55 x_{3,2} + 16 x_{3,3} + 67 x_{3,4} + 8 x_{3,5} + 91 x_{3,6} + 40 x_{4,1} + 54 x_{4,2} + 66 x_{4,3} + 22 x_{4,4} + 32 x_{4,5} + 25 x_{4,6} + 49 x_{5,1} + x_{5,2} + 17 x_{5,3} + 41 x_{5,4} + 14 x_{5,5} + 30 x_{5,6} + 44 x_{6,1} + 63 x_{6,2} + 10 x_{6,3} + 83 x_{6,4} + 46 x_{6,5} + 3 x_{6,6} = 419 $$

In [12]:

print(m)

Min 0
Subject to
 x[1,1] + x[1,2] + x[1,3] + x[1,4] + x[1,5] + x[1,6] = 1
 x[2,1] + x[2,2] + x[2,3] + x[2,4] + x[2,5] + x[2,6] = 1
 x[3,1] + x[3,2] + x[3,3] + x[3,4] + x[3,5] + x[3,6] = 1
 x[4,1] + x[4,2] + x[4,3] + x[4,4] + x[4,5] + x[4,6] = 1
 x[5,1] + x[5,2] + x[5,3] + x[5,4] + x[5,5] + x[5,6] = 1
 x[6,1] + x[6,2] + x[6,3] + x[6,4] + x[6,5] + x[6,6] = 1
 39 x[1,1] + 6 x[1,2] + 75 x[1,3] + 88 x[1,4] + 15 x[1,5] + 57 x[1,6] + 9 x[2,1] + 2 x[2,2] + 58 x[2,3] + 68 x[2,4] + 48 x[2,5] + 64 x[2,6] + 29 x[3,1] + 55 x[3,2] + 16 x[3,3] + 67 x[3,4] + 8 x[3,5] + 91 x[3,6] + 40 x[4,1] + 54 x[4,2] + 66 x[4,3] + 22 x[4,4] + 32 x[4,5] + 25 x[4,6] + 49 x[5,1] + x[5,2] + 17 x[5,3] + 41 x[5,4] + 14 x[5,5] + 30 x[5,6] + 44 x[6,1] + 63 x[6,2] + 10 x[6,3] + 83 x[6,4] + 46 x[6,5] + 3 x[6,6] = 419
 x[i,j] ∈ {0,1} ∀ i ∈ {1,2,…,5,6}, j ∈ {1,2,…,5,6}

In [13]:

status = solve(m)

Out[13]:

:Optimal

In [36]:

if status == :Infeasible
    println("Infeasible")
else
    SumL = 0
    for i = 1:6, j = 1:6
        if getValue(x[i,j]) > 0.999
            println("Lock ", i," = ", LockNumbers[i,j])
            SumL += LockNumbers[i,j]
        end
    end
end
println("Combination Sum = ", SumL)

Lock 1 = 88
Lock 2 = 68
Lock 3 = 91
Lock 4 = 40
Lock 5 = 49
Lock 6 = 83
Combination Sum = 419

Resources¶

• Iain Dunning | JuMP + Julia - Combination Lock Puzzle