CLISP中DFS实现八数码问题出现程序栈溢出求助

嘿，作为Lisp新手用DFS啃八数码遇到栈溢出真的太常见啦！我来帮你拆解下问题根源，再给你一套能跑通的优化方案～

问题根源分析 #

从你给出的代码片段来看，主要有两个核心问题导致栈溢出：

• 递归调用栈的限制：你用递归实现DFS，而八数码的搜索深度可能远超Lisp默认的程序栈大小，递归层数太多直接就爆栈了。
• 低效的状态检查：你用全局变量used记录已访问状态，还通过递归的is_used遍历整个列表做检查——不仅效率极低，而且递归遍历本身也会额外消耗栈空间，雪上加霜。
• 另外，全局变量的使用本身就不适合递归场景，很容易出现状态混乱的问题。

优化解决方案 #

1. 改用迭代式DFS替代递归DFS #

自己用列表模拟栈来存储待探索的状态，完全避开程序调用栈的限制，想探多深就探多深。

2. 用哈希表优化状态记录 #

把原来的used列表换成哈希表，查找已访问状态的时间复杂度从O(n)降到O(1)，既提升效率，又避免了递归遍历列表的额外栈消耗。

完整可运行代码示例 #

先补全你没写完的move函数，再给出迭代式DFS的实现：

;; 找到0的位置
(defun find-zero (lst)
  (position 0 lst))

;; 实现上下左右四个方向的移动
(defun move (lst direction)
  (let* ((zero (find-zero lst))
         (row (floor zero 3))
         (col (mod zero 3))
         (res (copy-list lst)))
    (cond
      ((eq direction 'L)
       (when (> col 0)
         (rotatef (elt res zero) (elt res (- zero 1)))))
      ((eq direction 'R)
       (when (< col 2)
         (rotatef (elt res zero) (elt res (+ zero 1)))))
      ((eq direction 'U)
       (when (> row 0)
         (rotatef (elt res zero) (elt res (- zero 3)))))
      ((eq direction 'D)
       (when (< row 2)
         (rotatef (elt res zero) (elt res (+ zero 3)))))
      (t nil))
    res))

;; 迭代式DFS实现八数码求解
(defun dfs-eight-puzzle (start goal)
  ;; 栈元素格式：(当前状态 到达该状态的路径)
  (let ((stack (list (list start nil)))
        ;; 哈希表存已访问状态，用equalp做相等判断
        (visited (make-hash-table :test #'equalp)))
    (setf (gethash start visited) t)
    (loop while stack do
          (let* ((current-node (pop stack))
                 (current-state (first current-node))
                 (path (second current-node)))
            ;; 找到目标状态，返回完整路径
            (if (equalp current-state goal)
                (return (reverse (cons current-state path))))
            ;; 生成四个方向的新状态，加入栈中
            (dolist (dir '(L R U D))
              (let ((next-state (move current-state dir)))
                (when (and next-state (not (gethash next-state visited)))
                  (setf (gethash next-state visited) t)
                  (push (list next-state (cons current-state path)) stack))))))
    ;; 如果遍历完所有状态都没找到解，返回nil
    nil))

代码关键点说明 #

• 迭代栈的使用：用stack列表模拟栈结构，每个元素保存当前状态和到达该状态的路径，完全脱离程序调用栈的限制。
• 哈希表优化：visited哈希表快速判断状态是否已访问，避免重复探索，大幅提升效率。
• 路径记录：每个栈元素附带路径信息，找到目标时直接返回完整的求解路径。

额外小提示 #

• 尽量避免使用全局变量，像你之前的used全局列表，在递归场景下很容易出现状态混乱，用函数内的局部变量+参数传递更安全。
• DFS虽然容易实现，但八数码问题中它不一定能找到最短路径，如果需要最优解，后续可以试试BFS或者A*算法～

内容的提问来源于stack exchange，提问作者mikha koltjia