CLISP dfs gets program stack overflow

This is a typical problem explained in some AI programming books. If you need to search a large / unbounded amount of states, you should not use recursion. Recursion in CL is limited by the stack depth. Some implementations can optimize tail recursion - but then you need architecture your code, so that it is tail recursive.

Typically a data structure for that will be called an agenda. It keeps the states still to explore. If you look at a state, you push all states to explore from there onto the agenda. Make sure the agenda is in some way sorted (this might determine if it is depths or breadths first). Then take the next state from the agenda and examine it. If the goal is reached, then you are done. If the agenda is empty before the goal is found, then there is no solution. Otherwise loop...

Your code, simplified, is

(setq *used* (list))

(defun move (position direction)
  (let* ( (zero (position 0 position)) 
          (row  (floor zero 3)) 
          (col  (mod   zero 3)) 
          (command (find direction `((L ,(> col 0) ,(- zero 1))
                                     (R ,(< col 2) ,(+ zero 1))
                                     (U ,(> row 0) ,(- zero 3))
                                     (D ,(< row 2) ,(+ zero 3)))
                         :key #'car)))
     (if (cadr command)
        (let ((res (copy-list position)))
           (rotatef (elt res zero) (elt res (caddr command)))
           res))))

(defun dfs-rec (cur_pos depth prev_pos)
  (write (length *used*)) (write '_) (write depth) (write '--)
  ; (terpri)
  (push cur_pos *used*)
  (let* ((dirs '(L R U D)))
    (loop for dir in dirs
          do (let ((new_pos (move cur_pos dir)))
               (if (and new_pos
                        (not (member new_pos *used* :test #'equalp)))
                 (dfs-rec new_pos (+ depth 1) cur_pos))))))

(print (dfs-rec '(0 1 2 3 4 5 6 7 8) 0 '()))

Instead of processing the four moves one by one while relying on recursion to keep track of what-to-do-next on each level, just push all the resulting positions at once to a to-do list, then pop and continue with the top one; repeating while the to-do list is not empty (i.e. there is something to do, literally):

(defun new-positions (position)
  (let* ( (zero (position 0 position)) 
          (row  (floor zero 3)) 
          (col  (mod   zero 3)) )
    (mapcan
         #'(lambda (command)
             (if (cadr command)
               (let ((res (copy-list position)))
                  (rotatef (elt res zero) (elt res (caddr command)))
                  (list res)))) 
         `((L ,(> col 0) ,(- zero 1))
           (R ,(< col 2) ,(+ zero 1))
           (U ,(> row 0) ,(- zero 3))
           (D ,(< row 2) ,(+ zero 3))) ))) 

; non-recursive dfs function skeleton
(defun dfs (start-pos &aux to-do curr new)
   (setf to-do (list start-pos))
   (loop while to-do
      do (progn (setf curr (pop to-do))
                (setf new (new-positions curr))
                (setf to-do (nconc new to-do)))))

This way there's no more info to keep track of, with recursion -- it's all in the to-do list.

This means the generated positions will be processed in the LIFO order, i.e. the to-do list will be used as a stack, achieving the depth-first search strategy.

If you'd instead append all the new positions on each step at the end of the to-do list, it'd mean it being used as a queue, in a FIFO order, achieving the breadth-first search.