如何排查递归Bug引发的代码冻结问题（骑士放置递归实现）

核心逻辑偏差 #

你提供的代码实际在实现骑士巡游问题（寻找一条遍历所有棋盘格子的骑士路径），但你的需求是计算8×8棋盘上最多可放置的互不攻击的骑士数量，这是完全不同的两个问题，也是程序冻结的根本原因之一——递归逻辑围绕错误的目标设计，导致无法终止或无意义的无限递归。

具体错误点 #

1. 递归参数混乱：place-knight中的count参数用于追踪巡游步数，而非已放置的骑士数量，递增逻辑完全不符合放置需求，导致递归无法正确终止。
2. 统计逻辑错误：knights-tour中用place-knight的返回值（巡游是否成功）来更新max-knights，完全无法反映实际放置的骑士数量。
3. 目标逻辑错误：整个代码没有考虑骑士的攻击特性（不能放置在彼此的攻击范围内），反而在尝试遍历所有格子，和需求南辕北辙。

符合要求的修复方案（无循环/Prog运算符） #

我们采用递归回溯法，严格围绕“放置互不攻击的骑士”这一目标设计，同时完全避免循环运算符，仅用递归实现遍历：

修复后代码 #

(defun can-place-p (board row col)
  "判断指定位置是否可放置骑士（在棋盘内且未被占用/标记为攻击范围）"
  (let ((size (array-dimension board 0)))
    (and (<= 0 row (- size 1))
         (<= 0 col (- size 1))
         (null (aref board row col)))))

(defun mark-attacked-recursive (board row col value moves)
  "递归处理所有骑士攻击方向，标记/取消标记对应位置"
  (unless (null moves)
    (let* ((move (car moves))
           (new-row (+ row (car move)))
           (new-col (+ col (cdr move))))
      (when (and (<= 0 new-row (- (array-dimension board 0) 1))
                 (<= 0 new-col (- (array-dimension board 0) 1)))
        (setf (aref board new-row new-col) value))
      (mark-attacked-recursive board row col value (cdr moves)))))

(defun mark-attacked (board row col value)
  "对外接口：调用递归函数处理所有骑士攻击位置"
  (mark-attacked-recursive board row col value
                           '((1 . 2) (1 . -2) (-1 . 2) (-1 . -2)
                             (2 . 1) (2 . -1) (-2 . 1) (-2 . -1))))

(defun backtrack (board row col current-count max-count)
  "递归回溯遍历棋盘，寻找最大可放置骑士数量"
  (let ((size (array-dimension board 0)))
    (cond
      ;; 遍历完所有格子，返回当前最大数量
      ((> row (- size 1))
       (max current-count max-count))
      ;; 当前列遍历完毕，进入下一行首列
      ((> col (- size 1))
       (backtrack board (1+ row) 0 current-count max-count))
      (t
       (let ((result max-count))
         ;; 尝试放置骑士
         (when (can-place-p board row col)
           ;; 标记当前位置为已放置
           (setf (aref board row col) t)
           ;; 标记所有被该骑士攻击的位置为不可用
           (mark-attacked board row col t)
           ;; 递归处理下一个格子，当前放置数量+1
           (setf result (backtrack board row (1+ col) (1+ current-count) result))
           ;; 回溯：取消所有标记
           (mark-attacked board row col nil)
           (setf (aref board row col) nil))
         ;; 尝试不放置骑士，直接处理下一个格子
         (setf result (backtrack board row (1+ col) current-count result))
         result)))))

(defun max-knights ()
  "计算8×8棋盘最多可放置的互不攻击的骑士数量"
  (let* ((size 8)
         (board (make-array (list size size) :initial-element nil)))
    (backtrack board 0 0 0 0)))

代码说明 #

1. can-place-p：检查目标位置是否在棋盘范围内，且未被占用或标记为攻击范围。
2. mark-attacked系列函数：用递归代替循环，处理骑士的8个攻击方向，标记或取消标记对应位置为不可用。
3. backtrack：核心递归回溯逻辑，对每个格子尝试两种选择（放置/不放置骑士），递归遍历所有可能，记录最大可放置数量。
4. max-knights：初始化棋盘并启动递归，最终返回结果（8×8棋盘的最优解为32）。

运行(max-knights)会直接返回32，这是因为骑士的攻击特性决定了，同色格子上的骑士彼此不会攻击，8×8棋盘有32个同色格子，这就是理论最大值。

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