/* Missionaries and cannibals problem in Picat. See http://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem Inspired by this Prolog code http://www-users.cs.york.ac.uk/~suresh/LAI/exercise1-sol/node3.html http://www-users.cs.york.ac.uk/~suresh/LAI/exercise1-sol/node6.html This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import planner. main => go. go => initial_state(Init), time(best_plan_bb(Init,L)), foreach(Move in L) writeln(Move) end, nl, writeln(len=L.length), nl. initial_state(Init) => Init=[3,3,left]. final(Goal) => Goal=[0,0,_]. legal([LM,LC,_]) ?=> %% left-hand side either missionaries greater-equals cannibals %% or no missionaries and some cannibals ( LM >= LC ; (LM == 0, not(LC==0)) ), %% right-hand side either missionaries greater-equals cannibals %% or no missionaries and some cannibals ( (3 - LM) >= (3 - LC) ; (LM == 3, not(LC==3)) ). %% Move 1 missionary across to right action([LM,LC,left],To,Move,Cost) ?=> To=[NLM,LC,right], Move=[m1_to_right,To], LM >= 1, NLM = LM - 1, legal([NLM,LC,right]),Cost=1. %% Move 1 missionary across to left action([LM,LC,left],To,Move,Cost) ?=> To=[NLM,LC,right], Move=[m1_to_left,To], (3 - LM) >= 1, NLM = LM + 1, legal([NLM,LC,right]),Cost=1. %% Move 1 cannibal across to right action([LM,LC,left],To,Move,Cost) ?=> To=[LM,NLC,right], Move=[c1_to_right,To], LC >= 1, NLC = LC - 1, legal([LM,NLC,right]),Cost=1. %% Move 1 cannibal across to left action([LM,LC,right],To,Move,Cost) ?=> To=[LM,NLC,left], Move=[c1_to_left,To], (3 - LC) >= 1, NLC = LC + 1, legal([LM,NLC,left]),Cost=1. %% Move 2 missionaries across to right action([LM,LC,left],To,Move,Cost) ?=> To=[NLM,LC,right], Move=[m2_to_right,To], LM >= 2, NLM = LM - 2, legal([NLM,LC,right]),Cost=1. %% Move 2 missionaries across to left action([LM,LC,right],To,Move,Cost) ?=> To=[NLM,LC,left], Move=[m2_to_left,To], (3 - LM) >= 2, NLM = LM + 2, legal([NLM,LC,right]),Cost=1. %% Move 2 cannibals across to right action([LM,LC,left],To,Move,Cost) ?=> To=[LM,NLC,right], Move=[c2_to_right,To], LC >= 2, NLC = LC - 2, legal([LM,NLC,right]),Cost=1. %% Move 2 cannibals across to left action([LM,LC,right],To,Move,Cost) ?=> To=[LM,NLC,left], Move=[c2_to_left,To], (3 - LC) >= 2, NLC = LC + 2, legal([LM,NLC,left]),Cost=1. %% Move 1 missionary + 1 cannibal across to right action([LM,LC,left],To,Move,Cost) ?=> To=[NLM,NLC,right], Move=[m1c1_to_right,To], LM >= 1, LC >= 1, NLM = LM - 1, NLC = LC - 1, legal([NLM,NLC,right]),Cost=1. %% Move 1 missionary + 1 cannibal across to left action([LM,LC,right],To,Move,Cost) => To=[NLM,NLC,left], Move=[m1c1_to_left,To], (3 - LM) >= 1, (3 - LC) >= 1, NLM = LM + 1, NLC = LC + 1, legal([NLM,NLC,left]),Cost=1.