fork download
copy 
  1. % to run the code in SWI-Prolog, do
  2. %        ?- ['missionaries_and_cannibals.pl'].
  3. %        ?- find.
  4.  
  5. % Represent a state as [CL,ML,B,CR,MR]
  6. start([3,3,left,0,0]).
  7. goal([0,0,right,3,3]).
  8.  
  9. legal(CL,ML,CR,MR) :-
  10. 	% is this state a legal one?
  11. 	ML>=0, CL>=0, MR>=0, CR>=0,
  12. 	(ML>=CL ; ML=0),
  13. 	(MR>=CR ; MR=0).
  14.  
  15. % Possible moves:
  16. move([CL,ML,left,CR,MR],[CL,ML2,right,CR,MR2]):-
  17. 	% Two missionaries cross left to right.
  18. 	MR2 is MR+2,
  19. 	ML2 is ML-2,
  20. 	legal(CL,ML2,CR,MR2).
  21.  
  22. move([CL,ML,left,CR,MR],[CL2,ML,right,CR2,MR]):-
  23. 	% Two cannibals cross left to right.
  24. 	CR2 is CR+2,
  25. 	CL2 is CL-2,
  26. 	legal(CL2,ML,CR2,MR).
  27.  
  28. move([CL,ML,left,CR,MR],[CL2,ML2,right,CR2,MR2]):-
  29. 	%  One missionary and one cannibal cross left to right.
  30. 	CR2 is CR+1,
  31. 	CL2 is CL-1,
  32. 	MR2 is MR+1,
  33. 	ML2 is ML-1,
  34. 	legal(CL2,ML2,CR2,MR2).
  35.  
  36. move([CL,ML,left,CR,MR],[CL,ML2,right,CR,MR2]):-
  37. 	% One missionary crosses left to right.
  38. 	MR2 is MR+1,
  39. 	ML2 is ML-1,
  40. 	legal(CL,ML2,CR,MR2).
  41.  
  42. move([CL,ML,left,CR,MR],[CL2,ML,right,CR2,MR]):-
  43. 	% One cannibal crosses left to right.
  44. 	CR2 is CR+1,
  45. 	CL2 is CL-1,
  46. 	legal(CL2,ML,CR2,MR).
  47.  
  48. move([CL,ML,right,CR,MR],[CL,ML2,left,CR,MR2]):-
  49. 	% Two missionaries cross right to left.
  50. 	MR2 is MR-2,
  51. 	ML2 is ML+2,
  52. 	legal(CL,ML2,CR,MR2).
  53.  
  54. move([CL,ML,right,CR,MR],[CL2,ML,left,CR2,MR]):-
  55. 	% Two cannibals cross right to left.
  56. 	CR2 is CR-2,
  57. 	CL2 is CL+2,
  58. 	legal(CL2,ML,CR2,MR).
  59.  
  60. move([CL,ML,right,CR,MR],[CL2,ML2,left,CR2,MR2]):-
  61. 	%  One missionary and one cannibal cross right to left.
  62. 	CR2 is CR-1,
  63. 	CL2 is CL+1,
  64. 	MR2 is MR-1,
  65. 	ML2 is ML+1,
  66. 	legal(CL2,ML2,CR2,MR2).
  67.  
  68. move([CL,ML,right,CR,MR],[CL,ML2,left,CR,MR2]):-
  69. 	% One missionary crosses right to left.
  70. 	MR2 is MR-1,
  71. 	ML2 is ML+1,
  72. 	legal(CL,ML2,CR,MR2).
  73.  
  74. move([CL,ML,right,CR,MR],[CL2,ML,left,CR2,MR]):-
  75. 	% One cannibal crosses right to left.
  76. 	CR2 is CR-1,
  77. 	CL2 is CL+1,
  78. 	legal(CL2,ML,CR2,MR).
  79.  
  80.  
  81. % Recursive call to solve the problem
  82. path([CL1,ML1,B1,CR1,MR1],[CL2,ML2,B2,CR2,MR2],Explored,MovesList) :- 
  83.    move([CL1,ML1,B1,CR1,MR1],[CL3,ML3,B3,CR3,MR3]), 
  84.    not(member([CL3,ML3,B3,CR3,MR3],Explored)),
  85.    path([CL3,ML3,B3,CR3,MR3],[CL2,ML2,B2,CR2,MR2],[[CL3,ML3,B3,CR3,MR3]|Explored],[ [[CL3,ML3,B3,CR3,MR3],[CL1,ML1,B1,CR1,MR1]] | MovesList ]).
  86.  
  87. % Solution found
  88. path([CL,ML,B,CR,MR],[CL,ML,B,CR,MR],_,MovesList):- 
  89. 	output(MovesList).
  90.  
  91. % Printing
  92. output([]) :- nl. 
  93. output([[A,B]|MovesList]) :- 
  94. 	output(MovesList), 
  95.    	write(B), write(' -> '), write(A), nl.
  96.  
  97. % Find the solution for the missionaries and cannibals problem
  98. find :- 
  99.    path([3,3,left,0,0],[0,0,right,3,3],[[3,3,left,0,0]],_).
Success #stdin #stdout #stderr 0.03s 6936KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
ERROR: '$runtoplevel'/0: Undefined procedure: program/0
   Exception: (3) program ? EOF: exit
https://ideone.com/9VU2l1
language:
Prolog (swi 7.6.4)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!