Skip to content

Instantly share code, notes, and snippets.

@saska-gist
Created November 24, 2018 17:31
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save saska-gist/dfe0a9cbba44cb97d9faa2293499cd45 to your computer and use it in GitHub Desktop.
# 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