大数据安全>> missionaries-and-cannibals>> 返回
项目作者： mgabilo

项目描述 ：
Missionaries and cannibals solver written in common Lisp
高级语言： Common Lisp
项目地址: git://github.com/mgabilo/missionaries-and-cannibals.git
创建时间： 2018-03-11T00:31:57Z
项目社区：https://github.com/mgabilo/missionaries-and-cannibals
开源协议：MIT License
下载


Missionaries and cannibals solver

This is a solver written in common Lisp for the missionaries and cannibals problem. From the Wikipedia article:

In the missionaries and cannibals problem, three missionaries and
three cannibals must cross a river using a boat which can carry at
most two people, under the constraint that, for both banks, if there
are missionaries present on the bank, they cannot be outnumbered by
cannibals (if they were, the cannibals would eat the missionaries).
The boat cannot cross the river by itself with no people on board.

In this program, the initial state and goal state are configurable,
as well as the number of missionaries and cannibals, and the number
of passengers the boat can hold.

Example usage

Run clisp from the command line and type the following within the interpreter.

  1. (load "mc.lisp")
  2. (mis-can)

You will be prompted to set up the problem.

  1. Enter the Initial State. 
  2. Format:  ((LEFT SIDE ATOMS) (RIGHT SIDE ATOMS))
  3. Example: ((M1 M2 M3 M4 C1 C2 C3 C4 B) ())

I will enter the following:

  1. ((M1 M2 M3 C1 C2 C3 B) ())

This stands for three missionaries and three cannibals (and the boat)
on the starting side. You will be prompted to enter the goal state.

  1. Enter the Goal State. 
  2. Format:  ((LEFT SIDE ATOMS) (RIGHT SIDE ATOMS))
  3. Example: (() (M1 M2 M3 M4 C1 C2 C3 C4 B))

I will enter the following:

  1. (() (M1 M2 M3 C1 C2 C3 B))

This stands for the three missionaries, three cannibals, and the boat
on the ending side. You will then be promted to enter the boat
capacity. I will enter 2.

The program produces the following output.

  1. SOLUTION GENERATED. THE PATH TO THE GOAL IS DISPLAYED.
  3. ((M1 M2 M3 C1 C2 C3 B) NIL)
  4. ((C3 M3 M2 M1) (B C2 C1))
  5. ((C2 B C3 M3 M2 M1) (C1))
  6. ((M1 M2 M3) (C3 B C2 C1))
  7. ((B C3 M1 M2 M3) (C1 C2))
  8. ((M3 C3) (M2 M1 B C1 C2))
  9. ((C1 B M2 M3 C3) (C2 M1))
  10. ((C3 C1) (M3 M2 B C2 M1))
  11. ((C2 B C3 C1) (M1 M2 M3))
  12. ((C1) (C3 B C2 M1 M2 M3))
  13. ((B C3 C1) (M3 M2 M1 C2))
  14. (NIL (C1 C3 B M3 M2 M1 C2))
  15. THE FOLLOWING STATES WERE GENERATED.
  17. ((NIL (C1 C3 B M3 M2 M1 C2)) 7 ((B C3 C1) (M3 M2 M1 C2)))
  18. (((M1 B C1) (M3 M2 C2 C3)) 4 ((C1) (C3 B C2 M1 M2 M3)))
  19. (((B C3 C1) (M3 M2 M1 C2)) 4 ((C1) (C3 B C2 M1 M2 M3)))
  20. (((C1) (C3 B C2 M1 M2 M3)) 6 ((C2 B C3 C1) (M1 M2 M3)))
  21. (((C2 B C3 C1) (M1 M2 M3)) 3 ((C3 C1) (M3 M2 B C2 M1)))
  22. (((C3 C1) (M3 M2 B C2 M1)) 5 ((C1 B M2 M3 C3) (C2 M1)))
  23. (((C1 B M2 M3 C3) (C2 M1)) 2 ((M3 C3) (M2 M1 B C1 C2)))
  24. (((M3 C3) (M2 M1 B C1 C2)) 5 ((B C3 M1 M2 M3) (C1 C2)))
  25. (((B C3 M1 M2 M3) (C1 C2)) 2 ((M1 M2 M3) (C3 B C2 C1)))
  26. (((M1 M2 M3) (C3 B C2 C1)) 4 ((C2 B C3 M3 M2 M1) (C1)))
  27. (((C2 B C3 M3 M2 M1) (C1)) 1 ((C3 M3 M2 M1) (B C2 C1)))
  28. (((C3 C2 M3 M2 M1) (B C1)) 2 ((M1 M2 M3 C1 C2 C3 B) NIL))
  29. (((C3 C2 M3 M2) (B C1 M1)) 3 ((M1 M2 M3 C1 C2 C3 B) NIL))
  30. (((C3 M3 M2 M1) (B C2 C1)) 3 ((M1 M2 M3 C1 C2 C3 B) NIL))
  31. (((M1 M2 M3 C1 C2 C3 B) NIL) 0 NIL)
  32. NIL

License

This project is licensed under the MIT License (see the LICENSE file for details)