Lesson 9

Write a lisp program solving the search problem beneath using depth first search. (A simplified version of the farmer, goat etc. problem, use "OR", but no need for "SAFE")
      S ---> A ---> B                        
      |      |                               
      |      |                               
      v      v                               
      C ---> D ---> G                        

      S ---> A ---> B                   >(depth 's nil)                  
      |      |                           1> (DEPTH S NIL)                
      |      |                             2> (RIGHT S)                  
      v      v                             <2 (RIGHT A)                  
      C ---> D ---> G                      2> (DEPTH A (S))              
                                             3> (RIGHT A)                
(defun right (state)                         <3 (RIGHT B)                
(cond ((equal state 's) 'a)                  3> (DEPTH B (A S))          
      ((equal state 'a) 'b)                    4> (RIGHT B)              
      ((equal state 'c) 'd)                    <4 (RIGHT NIL)            
      ((equal state 'd) 'g)                    4> (DEPTH NIL (B A S))    
      (t nil)))                                <4 (DEPTH NIL)            
                                               4> (DOWN B)               
(defun down (state)                            <4 (DOWN NIL)             
(cond ((equal state 's) 'c)                    4> (DEPTH NIL (B A S))    
      ((equal state 'a) 'd)                    <4 (DEPTH NIL)            
      (t nil)))                              <3 (DEPTH NIL)              
                                             3> (DOWN A)                 
(defun depth (s p)                           <3 (DOWN D)                 
  (cond ((null s) nil)                       3> (DEPTH D (A S))          
        ((equal s 'g)                 
           (reverse (cons s p)))               4> (RIGHT D)              
        ((member s p) nil)                     <4 (RIGHT G)              
        (t (or (depth (right s)       
                      (cons s p))              4> (DEPTH G (D A S))      
               (depth (down s)        
                      (cons s p))))))          <4 (DEPTH (S A D G))      
                                             <3 (DEPTH (S A D G))        
                                           <2 (DEPTH (S A D G))          
                                         <1 (DEPTH (S A D G))            
                                       (S A D G)                         
Search problems from page 9 in the handout, sorry they are in Swedish!
Last modified: Mon Apr 26 11:15:02 MEST 2004