Cannibals and missionaries help!!!
Posted: Fri Nov 01, 2013 6:29 am
Hello,
I am fairly new to lisp and need help with what seems to be a well known lisp problem. For one of my classes we are doing the cannibals and missionaries problem where there are 3 of both and 1 boat that can hold 2 people. The objective is to get all members across a river but if the missionaries ever outnumber the cannibals then the cannibals will be converted. We need to write a program to solve this problem, then have it solve it with a breadth or depth first search and a best-first search. The code below is what I have but I cannot get it to work please any help would be appreciated.
I am fairly new to lisp and need help with what seems to be a well known lisp problem. For one of my classes we are doing the cannibals and missionaries problem where there are 3 of both and 1 boat that can hold 2 people. The objective is to get all members across a river but if the missionaries ever outnumber the cannibals then the cannibals will be converted. We need to write a program to solve this problem, then have it solve it with a breadth or depth first search and a best-first search. The code below is what I have but I cannot get it to work please any help would be appreciated.
Code: Select all
;; Name:
;; Project Name: Cannibals and Missionaries
;; Description : To safely transport all members across the river
;; to the other side
(defun solve-cm (state goal)
(path state goal nil))
;; Define the start state
(setf *start* '(3 3 0 0 start-bank))
;; Define the goal state
(setf *goal* '(0 0 3 3 goal-bank))
;; Safe returns nil if a state is not safe; it returns the state unchanged if it is safe.
(defun safe (state)
(cond ((or
(> (missionaries-at-start state)(cannibals-at-start state))
(> (missionaries-at-goal state)(cannibals-at-goal state))
(> (cannibals-at-start state) 0)
(< (cannibals-at-start state) 3)
nil))
(t( state)) ) )
;; The recursive path algorithm searches the space in a depth first fashion.
(defun path (state goal been-list)
(cond ((null state) nil)
((equal state goal) (reverse (cons state been-list)))
((not (member state been-list :test #'equal))
(or (path (move-two-cannibals state) goal (cons state been-list))
(path (move-two-missionaries state) goal (cons state been-list))
(path (move-one-cannibal state) goal (cons state been-list))
(path (move-one-missionary state) goal (cons state been-list))
(path (move-one-of-each state) goal (cons state been-list))
))))
;; These functions define legal moves in the state space. The take
;; a state as argument, and return the state produced by that operation.
(defun move-two-cannibals(state)
(cond
((equal (boat-position state) 'start-bank)
(safe (make-state
(- (cannibals-at-start state) 2)
(missionaries-at-start state)
(+ (cannibals-at-goal state) 2)
(missionaries-at-goal state)
(opposite (boat-poition state))
)))
((equal (boat-position state) 'goal-bank)
(safe (make-state
(+ (cannibals-at-start state) 2)
(missionaries-at-start state)
(- (cannibals-at-goal state) 2)
(missionaries-at-goal state)
(opposite (boat-poition state))
)))
))
(defun move-one-cannibal(state)
(cond
((equal (boat-position state) 'start-bank)
(safe (make-state
(- (cannibals-at-start state) 1)
(missionaries-at-start state)
(+ (cannibals-at-goal state) 1)
(missionaries-at-goal state)
(opposite (boat-poition state))
)))
((equal (boat-position state) 'goal-bank)
(safe (make-state
(+ (cannibals-at-start state) 1)
(missionaries-at-start state)
(- (cannibals-at-goal state) 1)
(missionaries-at-goal state)
(opposite (boat-poition state))
)))
))
(defun move-two-missionaries(state)
(cond
((equal (boat-position state) 'start-bank)
(safe (make-state
(cannibals-at-start state)
(- (missionaries-at-start state) 2)
(cannibals-at-goal state)
(+ (missionaries-at-goal state) 2)
(opposite (boat-poition state))
)))
((equal (boat-position state) 'goal-bank)
(safe (make-state
(cannibals-at-start state)
(+ (missionaries-at-start state) 2)
(cannibals-at-goal state)
(- (missionaries-at-goal state) 2)
(opposite (boat-poition state))
)))
))
(defun move-one-missionary(state)
(cond
((equal (boat-position state) 'start-bank)
(safe (make-state
(cannibals-at-start state)
(- (missionaries-at-start state) 1)
(cannibals-at-goal state)
(+ (missionaries-at-goal state) 1)
(opposite (boat-poition state))
)))
((equal (boat-position state) 'goal-bank)
(safe (make-state
(cannibals-at-start state)
(+ (missionaries-at-start state) 1)
(cannibals-at-goal state)
(- (missionaries-at-goal state) 1)
(opposite (boat-poition state))
)))
))
(defun move-one-of-each(state)
(cond
((equal (boat-position state) 'start-bank)
(safe (make-state
(- (cannibals-at-start state) 1)
(- (missionaries-at-start state) 1)
(+ (cannibals-at-goal state) 1)
(+ (missionaries-at-goal state) 1)
(opposite (boat-poition state))
)))
((equal (boat-position state) 'goal-bank)
(safe (make-state
(+ (cannibals-at-start state) 1)
(+ (missionaries-at-start state) 1)
(- (cannibals-at-goal state) 1)
(- (missionaries-at-goal state) 1)
(opposite (boat-poition state))
)))))
(defun opposite (boat-position)
(cond ((equal boat-position 'start-bank) 'goal-bank)
((equal boat-position 'goal-bank) 'start-bank)))
;; These functions define states of the world as an abstract data type.
(defun make-state (cs ms cg mg boat-position)
(list cs ms cg mg boat-position))
(defun cannibals-at-start ( state )
(first state))
(defun missionaries-at-start ( state )
(second state))
(defun cannibals-at-goal ( state )
(third state))
(defun missionaries-at-goal ( state )
(fourth state))
(defun boat-position ( state )
(fifth state))