;;;  search.scm    Dave Reed    9/04/08
;;;
;;;  Implements the following search strategies for state spaces:
;;;    depth-first search (DFS)
;;;    depth-first search with cycle checking (dfs-nocycles)
;;;    breadth-first search (BFS)depth-first
;;;    breadth-first search with cycle checking (BFS-nocycles)
;;;    depth-first search with iterative deepening (DFS-deepening)
;;;
;;;  These functions assume that the GET-MOVES function has been defined for 
;;;  a given state space:  (GET-MOVES state) returns a list of all new 
;;;  states reachable from state.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (DFS startState goalState)
  
  (define (extend path moves)
    (cond ((equal? (car path) goalState) path)
          ((null? moves) #f)
          (else (or (extend (cons (car moves) path) (GET-MOVES (car moves)))
                    (extend path (cdr moves))))))
  
  (extend (list startState) (GET-MOVES startState)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (DFS-nocycles startState goalState)
  
  (define (extend path moves)
    (cond ((equal? (car path) goalState) path)
          ((null? moves) #f)
          (else (or (and (not (member (car moves) path))
                         (extend (cons (car moves) path) (GET-MOVES (car moves))))
                    (extend path (cdr moves))))))
  
  (extend (list startState) (GET-MOVES startState)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  
(define (BFS startState goalState)
  
  (define (BFS-paths paths)
    (cond ((null? paths) #f)
          ((equal? (caar paths) goalState) (car paths))
          (else (BFS-paths (append (cdr paths)
                                   (extend-all (car paths) (GET-MOVES (caar paths))))))))
  
  (define (extend-all path nextStates)
    (if (null? nextStates) 
        '()
        (cons (cons (car nextStates) path)
              (extend-all path (cdr nextStates)))))
  
  (BFS-paths (list (list startState))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  
(define (BFS-nocycles startState goalState)
  
  (define (BFS-paths paths)
    (cond ((null? paths) #f)
          ((equal? (caar paths) goalState) (car paths))
          (else (BFS-paths (append (cdr paths)
                                   (extend-all (car paths) (GET-MOVES (caar paths))))))))
  
  (define (extend-all path nextStates)
    (cond ((null? nextStates) '())
          ((member (car nextStates) path) (extend-all path (cdr nextStates)))
          (else (cons (cons (car nextStates) path)
                      (extend-all path (cdr nextStates))))))
  
  (BFS-paths (list (list startState))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (DFS-deepening startState goalState)
  
  (define (DFS-bounded bound)
    (or (extend (list startState) (GET-MOVES startState) bound)
        (DFS-bounded (+ bound 1))))
  
  (define (extend path moves depthBound)
    (cond ((> (length path) depthBound) #f)
          ((equal? (car path) goalState) path)
          ((null? moves) #f)
          (else (or (and (not (member (car moves) path))
                         (extend (cons (car moves) path) 
                                 (GET-MOVES (car moves)) depthBound))
                    (extend path (cdr moves) depthBound)))))
  
  (DFS-bounded  1))