(defun main NIL
   (print '(Enter the number N))
   (setf N (read))
   (setf stack NIL)
   (searching N N 'L stack)
)

(defun searching (miss cann side stack)
   (cond
         ((not (issafe miss cann)) NIL)	                  ; if miss are not safe, return         
         ((goalstate (cons (list miss cann side ) stack)) ; if the goal has been reached, return
	 (print '(FOUND SOLUTION))	
         (print (reverse (cons (list miss cann side) stack)))
         T)
	 ((havebeen (list miss cann side) stack) NIL)     ; if we've been here, return
                  
         ;-------------------- RECURSIVE CALLS TO NEXT STATES -------------------------
         (T (cond ((equal side 'L)     ;======== BOAT ON THE LEFT =========
            (searching (- miss 1) (- cann 1) 'R (cons 'MCR (cons (list miss cann side) stack)))
            (searching (- miss 2) cann 'R (cons 'MMR (cons (list miss cann side) stack)))
            (searching (- miss 1) cann 'R (cons 'MR (cons (list miss cann side) stack)))
            (searching miss (- cann 2) 'R (cons 'CCR (cons (list miss cann side) stack)))
            (searching miss (- cann 1) 'R (cons 'CR (cons (list miss cann side) stack)))
	 ))
	 (cond ((equal side 'R)        ;======== BOAT ON THE RIGHT ========
            (searching (+ miss 1) (+ cann 1) 'L (cons 'MCL (cons (list miss cann side) stack)))
            (searching (+ miss 2) cann 'L (cons 'MML (cons (list miss cann side) stack)))
	    (searching (+ miss 1) cann 'L (cons 'ML (cons (list miss cann side) stack)))
	    (searching miss (+ cann 2) 'L (cons 'CCL (cons (list miss cann side) stack)))
	    (searching miss (+ cann 1) 'L (cons 'CL (cons (list miss cann side) stack)))
	 ))
     NIL)))

(defun goalstate (thelist)			; have we reached the goal state yet?
   (cond ((equal (car thelist) '(0 0 R)) T)))

(defun havebeen (cur_state thelist)	        ; have we been to this state before?
   (cond ((member cur_state thelist :test #'equal) T)))

(defun issafe (miss cann)	   	        ; are the missionaries safe?
   (cond					;
         ((> miss N) NIL) ((> cann N) NIL)	; number exceeded the original given
         ((< miss 0) NIL) ((< cann 0) NIL)	; negative number not allowed
         ((eql miss cann) T)			; #miss == #cann
         ((eql miss 0) T)			; all the miss are on the Right side
         ((eql miss N) T)			; all the miss are on the Left side
         (T NIL)				; if all fails, return NIL
 ))