Hiker Problem

Hiker Assignment¶

Who Hikes Alone?¶

http://lpl.unifr.ch/puzzles/lplmodels/puzzles/hikers.1.pdf

In [2]:

using JuMP

m = Model()

@variable(m, Group[i=1:4,j=1:17], Bin)

# Group Size 
@constraint(m, sum{Group[1,j],j=1:17} == 1)
@constraint(m, sum{Group[3,j],j=1:17} == 3)

# Each person in one group only
for j = 1:17
    @constraint(m, sum{Group[i,j],i=1:4}==1)
end

# Individual Hiker Constraints
# This code could be much more compact, but the constraints are
# added a few at a time, with print statements for double-
# checking the constaints against the original problem statement.

# ABCDEFGHIJKLMNOPQ
# 12345678901234567
LetterLookup = ['A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q']

# A <> F,G,H,O
for j in (6,7,8,15)
    for i = 1:4
        @constraint(m,Group[i,1]+Group[i,j] <= 1)
    end
    println(LetterLookup[1]," not with ",LetterLookup[j])
end

# B <> A,C,G,H
for j in (1,3,7,8)
    for i = 1:4
        @constraint(m,Group[i,2]+Group[i,j] <= 1)
    end
    println(LetterLookup[2]," not with ",LetterLookup[j])
end

# C <> D,J,K,M
for j in (4,10,11,13)
    for i = 1:4
        @constraint(m,Group[i,3]+Group[i,j] <= 1)
    end
    println(LetterLookup[3]," not with ",LetterLookup[j])
end

# D <> C,E,P,Q
for j in (3,5,16,17)
    for i = 1:4
        @constraint(m,Group[i,4]+Group[i,j] <= 1)
    end
    println(LetterLookup[4]," not with ",LetterLookup[j])
end

# E <> D,F,K,O
for j in (4,6,11,15)
    for i = 1:4
        @constraint(m,Group[i,5]+Group[i,j] <= 1)
    end
    println(LetterLookup[5]," not with ",LetterLookup[j])
end

# F <> A,E,G,H
for j in (1,5,7,8)
    for i = 1:4
        @constraint(m,Group[i,6]+Group[i,j] <= 1)
    end
    println(LetterLookup[6]," not with ",LetterLookup[j])
end

# G <> C,E,F,J
for j in (3,5,6,10)
    for i = 1:4
        @constraint(m,Group[i,7]+Group[i,j] <= 1)
    end
    println(LetterLookup[7]," not with ",LetterLookup[j])
end

# H <> E,F,I,K
for j in (5,6,9,11)
    for i = 1:4
        @constraint(m,Group[i,8]+Group[i,j] <= 1)
    end
    println(LetterLookup[8]," not with ",LetterLookup[j])
end

# I <> A,G,K,L
for j in (1,7,11,12)
    for i = 1:4
        @constraint(m,Group[i,9]+Group[i,j] <= 1)
    end
    println(LetterLookup[9]," not with ",LetterLookup[j])
end

# J <> G,I,L,P
for j in (7,9,12,16)
    for i = 1:4
        @constraint(m,Group[i,10]+Group[i,j] <= 1)
    end
    println(LetterLookup[10]," not with ",LetterLookup[j])
end

# K <> G,H,L,Q
for j in (7,8,12,17)
    for i = 1:4
        @constraint(m,Group[i,11]+Group[i,j] <= 1)
    end
    println(LetterLookup[11]," not with ",LetterLookup[j])
end

# L <> J,M,N,O
for j in (10,13,14,15)
    for i = 1:4
        @constraint(m,Group[i,12]+Group[i,j] <= 1)
    end
    println(LetterLookup[12]," not with ",LetterLookup[j])
end

# M <> A,C,L,N
for j in (1,3,12,14)
    for i = 1:4
        @constraint(m,Group[i,13]+Group[i,j] <= 1)
    end
    println(LetterLookup[13]," not with ",LetterLookup[j])
end

# N <> D,L,O,P
for j in (4,12,15,16)
    for i = 1:4
        @constraint(m,Group[i,14]+Group[i,j] <= 1)
    end
    println(LetterLookup[14]," not with ",LetterLookup[j])
end

# O <> E,L,N,Q
for j in (5,12,14,17)
    for i = 1:4
        @constraint(m,Group[i,15]+Group[i,j] <= 1)
    end
    println(LetterLookup[15]," not with ",LetterLookup[j])
end

# P <> D,J,M,N
for j in (4,10,13,14)
    for i = 1:4
        @constraint(m,Group[i,16]+Group[i,j] <= 1)
    end
    println(LetterLookup[16]," not with ",LetterLookup[j])
end

# Q <> D,K,N,O
for j in (4,11,14,15)
    for i = 1:4
        @constraint(m,Group[i,17]+Group[i,j] <= 1)
    end
    println(LetterLookup[17]," not with ",LetterLookup[j])
end

status = solve(m)
#print(m)

println("\nSolution is:")
for j = 1:17
    println(LetterLookup[j],"  ",
    round(Int,getvalue(Group[1,j]))," ",
    round(Int,getvalue(Group[2,j]))," ",
    round(Int,getvalue(Group[3,j]))," ",
    round(Int,getvalue(Group[4,j])))  
end

A not with F
A not with G
A not with H
A not with O
B not with A
B not with C
B not with G
B not with H
C not with D
C not with J
C not with K
C not with M
D not with C
D not with E
D not with P
D not with Q
E not with D
E not with F
E not with K
E not with O
F not with A
F not with E
F not with G
F not with H
G not with C
G not with E
G not with F
G not with J
H not with E
H not with F
H not with I
H not with K
I not with A
I not with G
I not with K
I not with L
J not with G
J not with I
J not with L
J not with P
K not with G
K not with H
K not with L
K not with Q
L not with J
L not with M
L not with N
L not with O
M not with A
M not with C
M not with L
M not with N
N not with D
N not with L
N not with O
N not with P
O not with E
O not with L
O not with N
O not with Q
P not with D
P not with J
P not with M
P not with N
Q not with D
Q not with K
Q not with N
Q not with O

Solution is:
A  0 1 0 0
B  0 0 0 1
C  0 1 0 0
D  0 0 0 1
E  0 1 0 0
F  0 0 0 1
G  0 0 1 0
H  0 0 1 0
I  1 0 0 0
J  0 0 0 1
K  0 0 0 1
L  0 1 0 0
M  0 0 0 1
N  0 0 1 0
O  0 0 0 1
P  0 1 0 0
Q  0 1 0 0

---

Hiker "I" is the lone hiker.
The group of three hikers is: G,H,N