Created
November 24, 2018 17:31
Star
You must be signed in to star a gist
A scip model for solving the puzzle at https://www.puzzleprime.com/brain-teasers/deduction/missionaries-cannibals/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# A scip model for solving the puzzle at | |
# https://www.puzzleprime.com/brain-teasers/deduction/missionaries-cannibals/ | |
param ncrossings := 30; | |
set people := { 'M1','M2','M3', 'C1','C2','C3' }; # 3 missionaries/3 cannibals | |
defbool missionary(p):= (p=='M1' or p=='M2' or p=='M3'); | |
defbool cannibal(p) := (not(missionary(p))); | |
set xings := { 1..ncrossings }; # river crossings | |
var x[xings * people] binary; # who cross the river every time | |
var A[xings * people] binary; # which people are on bank A every time | |
var B[xings * people] binary; # which people are on bank B every time | |
# a person is either on bank A or B | |
subto ab: forall <c,f> in xings*people do A[c,f]==(1-B[c,f]); | |
# in the beginning everyone is on bank A | |
subto a1: forall <p> in people do A[1,p]==1; | |
# at the end everyone is on bank B | |
subto b1: forall <p> in people do B[ncrossings,p]==1; | |
# only 1 or 2 people can cross the river at the same time | |
subto x1: forall <c> in xings do sum <f> in people: x[c, f] <= 2; | |
# if not everyone is on bank B, someone must cross the river | |
subto x2: forall <c> in xings do vif sum <f> in people: A[c,f] >= 1 | |
then sum <f> in people: x[c, f] >= 1 end; | |
# as soon as everyone is on bank B, no more river crossings | |
subto x3: forall <c> in xings do vif sum <f> in people: A[c,f] == 0 | |
then sum <f> in people: x[c, f] == 0 end; | |
# | |
# continuity | |
# | |
# from A to B | |
subto c1: forall <c,f> in xings*people with c<ncrossings and (c mod 2)==1 | |
do x[c,f] <= A[c,f]; | |
subto c2: forall <c,f> in xings*people with c<ncrossings and (c mod 2)==1 | |
do B[c+1,f] == B[c,f] + x[c,f] ; | |
# from B to A | |
subto c3: forall <c,f> in xings*people with c<ncrossings and (c mod 2)==0 | |
do x[c,f] <= B[c,f]; | |
subto c4: forall <c,f> in xings*people with c<ncrossings and (c mod 2)==0 | |
do A[c+1,f] == A[c,f] + x[c,f]; | |
# if on one of the two banks of the river the missionaries get outnumbered | |
# by the cannibals, they will get eaten | |
# (the missionary is always safe in the boat) | |
subto mc1: forall <c> in xings do | |
vif sum <f> in people with missionary(f): A[c,f] >= 1 | |
then | |
sum <f> in people with missionary(f): A[c,f] >= | |
sum <f> in people with cannibal(f): A[c,f] | |
end; | |
subto mc2: forall <c> in xings do | |
vif sum <f> in people with missionary(f): B[c,f] >= 1 | |
then | |
sum <f> in people with missionary(f): B[c,f] >= | |
sum <f> in people with cannibal(f): B[c,f] | |
end; | |
var total_number_of_crossings integer; | |
var rcrossings[xings] binary; # did anyone cross the river at this time? | |
subto r11: forall <c> in xings do | |
vif (sum <p> in people: x[c,p]) >= 1 | |
then rcrossings[c]==1 | |
else rcrossings[c]==0 end; | |
subto tt: total_number_of_crossings == (sum <c> in xings: rcrossings[c]); | |
minimize cost: total_number_of_crossings; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment