; the following search function does breadth-first search
; of floor-plan  from START to FINISH.
; if the value of print is 2 it prints the queue at each cycle
; if the value of print is 1 it prints the queue length
; if the value of print is any other number it prints nothing

(defun search (start finish print)
  (do ((queue (list (list start)) (append (cdr queue) expansion))
       (expansion))
      ((cond ((null queue) (return nil))
             ((equal finish (caar queue)) (return (reverse (car queue))))))
      (setq expansion (expand (car queue)))
      (cond ((= print 2)(print  queue))
            ((= print 1)(print (length queue))))))

(defun expand (path)
  (remove nil 
          (mapcar #'(lambda (x) 
                      (cond ((not (member x path)) (cons x path))))
                  (cdr (assoc (car path) floor-plan)))))

(setq floor-plan
    '(   (d5 i7) (i6 h9 h10) (h10 i6 i7) (i7 d5 h13 h11 h10)
  	(h11 i7 i8) (i8 h11 h12) (h9 i6 i5) (h13 i7 i4)
	(h12 i8 i1) (d1 h2) (h2 d1 i1) (i1 h1 h2 h12) (h1 i1 i2)
  	(i2 h3 h1 h6) (h6 i2 i4) (i4 h13 h6 h7) (h7 i4 i5)
	(i5 h9 h7 h8) (h8 i5 d4) (d4 h8) (h3 i2 i3)
	(d2 h4) (h4 d2 i3) (i3 h4 h3 h5) (h5 i3 d3) (d3 h5)
    )
)

;