'finding the digits' 在 Common Lisp 中使用递归问题的意外结果
Unexpected results for 'finding the digits' problem using recursion in Common Lisp
“求数字问题”是这样的：
Find unique decimal digits A, B, C such that
CCC
+ BBB
+ AAA
= CAAB
为了在 Common Lisp 中使用递归来解决它，我编写了以下代码：
(defun find! ()
(found? 0 ;; initially point to the number 1
'(1 2 3) ;; initial list
'() ;; initially no numbers found
3 ;; numbers list width is 3
) )
(defun found? (index lst occupied width)
(if (< index (1- width))
(do ( (j 1 (1+ j) ) )
( (> j 9) lst)
(unless (some (lambda (x) (= x j)) occupied)
(setf (nth index lst) j)
(push j occupied)
(if (found? (1+ index) lst occupied width) ;; recursion happens here
lst
(setf occupied (remove j occupied)))))
(do ( (j 1 (1+ j) ) )
( (> j 9) lst)
(unless (some (lambda (x) (= x j)) occupied)
(setf (nth index lst) j)
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+
(mapcar
(lambda (x y) (* x y))
'(1000 100 10 1)
(list (third lst) (first lst)
(first lst) (second lst))))))
(if (= lefthnd rghthnd)
lst
'nil))))))
传递的结果（lst）是(9 9 9)
预期结果 (lst) 是 (9 8 1)，意思是 A=9、B=8、C=1，因此等式 CCC + BBB + AAA = CAAB 成立，即
111 ; CCC
+ 888 ; BBB
+ 999 ; AAA
= 1998 ; CAAB
我应该更改代码的哪些部分才能得到预期的结果？有人可以修复代码吗？请注意，必须使用递归。只有一行递归就足够了，比如 ;; recursion happens here 注释所在的行。
修复此代码的最少修改是什么？
您似乎可以使用另一种语言解决问题，所以我不会花太多时间谈论所使用的problem/algorithm（您已经知道该怎么做）。但是，由于您正在学习 Common Lisp，我将提供一个典型的 Whosebug 答案，并提供很多您没有要求的建议！
- 修正你的 parentheses/indentation，这将使你的代码更清晰。
- 将您的代码拆分为更多、更小的函数。您正在使用具有多个参数的递归函数解决问题，并且该函数超过二十行。这使得阅读和调试变得非常困难。
- 使用built-in函数：
(some (lambda (x) (= x j)) occupied) == (member j occupied :test #'=)，在那种情况下，它仍然可以在不指定测试的情况下工作（这在技术上是错误的，这两个函数并不return相同的东西，但您只将结果用作布尔值，因此这实际上是同一件事）。
(mapcar (lambda (x y) (* x y)) ...) 只是 (mapcar #'* ...)'nil == nil，不用引用。使用 () 而不是 nil 来表示空列表（与布尔值相对）也是（可以说）很好的风格，但这确实是一个小问题。
就算法而言，如果您使用更小的函数重写它，我将很乐意提供帮助。目前，它确实难以阅读和理解。
编辑：
我仍然试图花时间重写代码并提出一个更简洁的解决方案。
TL;DR：这是最终结果，对您的代码进行了“最小”修改：
(defun find! ()
(found? 0 (list 1 2 3) () 3))
(defun compute-lefthand (list)
(* 111 (reduce #'+ list)))
(defun compute-righthand (list)
(reduce #'+ (mapcar #'*
'(1000 100 10 1)
(list (third list)
(first list)
(first list)
(second list)))))
(defun check-solution (list)
(when (= (compute-lefthand list)
(compute-righthand list))
list))
(defun try-solution (j index list occupied width)
(unless (member j occupied)
(setf (nth index list) j)
(found? (1+ index)
list
(cons j occupied)
width)))
(defun found? (index lst occupied width)
(if (= index width)
(check-solution lst)
(dotimes (j 10)
(when (try-solution j index lst occupied width)
(return lst)))))
除了我最初回答中已经提到的样式问题之外，您的初始代码还存在不稳定的控制流。很难确定 什么 真的被每个递归调用 return 编辑了，因为 你没有更小的函数，所以它不清楚每个部分的目标是什么，信息如何从递归调用传递到父级，修改了哪些对象等等。
现在，我的代码不是最干净的，我可能不会使用这种策略来解决问题，但我尽量保持与您的初始代码接近。主要区别：
- 我把事情分成更小的功能。这让一切都变得更清晰，最重要的是，更容易测试。每个功能 return 都清楚。例如，如果
check-solution return 表示正确的解决方案，则列表为列表，否则为 nil；我使用 when 而不是 if 控制结构这一事实清楚地表明了这一点。
- 我把
do换成dotimes也更清楚；正在变化的变量及其在每一步的变化方式现在立即可见。
- 我不使用
do/dotimes宏的&optional return参数，而是使用明确的return。然后可以清楚地确定什么正在returned，以及什么时候。
- 我不使用
push/pop 来修改我的列表。您正在使用递归策略，因此您的“修改”应该采用传递给函数的不同参数的形式。再一次，通过准确了解每个函数对每个参数的作用，它使程序推理变得更容易。一个更好的解决方案也是删除对 setf 的调用，而是使用 (cons <smtg> lst) 作为递归调用的参数，但这很好。
你的初始程序中的错误可能是因为你的函数并不像你想的那样return，因为你有几个连续的表达式，每个表达式在不同的情况下被调用，return值本身是错误的，因为它们的顺序不正确，并且使用 do 的可选 return 值在错误的时间修改对象和 return 它们。
TL;DR: 把事情分开；让每个函数只做一件事情。
您的代码
(defun find! ()
(found? 0 ;; initially show the number 1
'(1 2 3) ;; initial list
'() ;; initially no numbers found
3 ;; numbers list width is 3
) )
(defun found? (index lst occupied width)
(if (< index (1- width))
(do ( (j 1 (1+ j) ) )
( (> j 9) lst)
(unless (some (lambda (x) (= x j)) occupied)
(setf (nth index lst) j)
(push j occupied)
(if (found? (1+ index) lst occupied width) ;; recursion
lst
(setf occupied (remove j occupied)))))
(do ( (j 1 (1+ j) ) )
( (> j 9) lst)
(unless (some (lambda (x) (= x j)) occupied)
(setf (nth index lst) j)
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+ (mapcar (lambda (x y) (* x y))
'(1000 100 10 1)
(list (third lst) (first lst) (first lst) (second lst))
))))
(if (= lefthnd rghthnd)
lst
'nil))))))
缩进和注释样式：end-of-line注释使用单个分号，
对齐 non-body 个参数，将正文缩进两个空格
(defun find! ()
(found? 0 ; initially show the number 1
'(1 2 3) ; initial list
'() ; initially no numbers found
3)) ; numbers list width is 3
(defun found? (index lst occupied width)
(if (< index (1- width))
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (some (lambda (x) (= x j)) occupied)
(setf (nth index lst) j)
(push j occupied)
(if (found? (1+ index) lst occupied width) ; recursion
lst
(setf occupied (remove j occupied)))))
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (some (lambda (x) (= x j)) occupied)
(setf (nth index lst) j)
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+
(mapcar (lambda (x y) (* x y))
'(1000 100 10 1)
(list (third lst)
(first lst)
(first lst)
(second lst))))))
(if (= lefthnd rghthnd)
lst
'nil))))))
使用更有说服力的谓词：find 或 member。不要将 * 包裹在 lambda 中
没有其他的。 （我会把 find! 放在一边。）
(defun found? (index lst occupied width)
(if (< index (1- width))
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(push j occupied)
(if (found? (1+ index) lst occupied width) ; recursion
lst
(setf occupied (remove j occupied)))))
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+
(mapcar #'*
'(1000 100 10 1)
(list (third lst)
(first lst)
(first lst)
(second lst))))))
(if (= lefthnd rghthnd)
lst
'nil))))))
do 的正文没有 return 任何内容。有很多死代码，
我们现在删除：
(defun found? (index lst occupied width)
(if (< index (1- width))
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(push j occupied)
(unless (found? (1+ index) lst occupied width) ; recursion
(setf occupied (remove j occupied)))))
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)))))
我们可以有条件地推送，而不是推送然后有条件地删除：
(defun found? (index lst occupied width)
(if (< index (1- width))
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(when (found? (1+ index) lst occupied width) ; recursion
(push j occupied))))
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)))))
虽然它在性能上有所不同，但将外部条件
进入内部主体使其在这里更具可读性：
(defun found? (index lst occupied width)
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(when (and (< index (1- width))
(found? (1+ index) lst occupied width)) ; recursion
(push j occupied)))))
除了几次数到 9 之外，这没有任何作用，这似乎是一致的
根据您的发现。
我猜您想 return 从死代码中提取一些东西。你可能
想为此使用 return-from。
(defun found? (index lst occupied width)
(if (< index (1- width))
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(push j occupied)
(if (found? (1+ index) lst occupied width) ; recursion
(return-from found? lst)
(setf occupied (remove j occupied)))))
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+
(mapcar #'*
'(1000 100 10 1)
(list (third lst)
(first lst)
(first lst)
(second lst))))))
(when (= lefthnd rghthnd)
(return-from found? lst)))))))
这个returns(1 2 9)，这是错误的。问题似乎是你
return 列表即使你 运行 超过 9，但你想 return nil 然后，
因为你没有找到任何东西。
(defun found? (index lst occupied width)
(if (< index (1- width))
(do ((j 1 (1+ j)))
((> j 9) nil) ; <- nothing found
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(push j occupied)
(if (found? (1+ index) lst occupied width) ; recursion
(return-from found? lst)
(setf occupied (remove j occupied)))))
(do ((j 1 (1+ j)))
((> j 9) nil) ; <- nothing found
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+
(mapcar #'*
'(1000 100 10 1)
(list (third lst)
(first lst)
(first lst)
(second lst))))))
(when (= lefthnd rghthnd)
(return-from found? lst)))))))
这个returns(9 8 1)，是正确的。现在我似乎明白了什么
你正在尝试做，让我们再重构一点。而不是推动和
从占用的列表中删除，只需使用新元素创建一个新列表
短暂在前：
(defun found? (index lst occupied width)
(if (< index (1- width))
(do ((j 1 (1+ j)))
((> j 9) nil)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(when (found? (1+ index) ; recursion
lst
(cons j occupied)
width)
(return-from found? lst))))
(do ((j 1 (1+ j)))
((> j 9) nil)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+
(mapcar #'*
'(1000 100 10 1)
(list (third lst)
(first lst)
(first lst)
(second lst))))))
(when (= lefthnd rghthnd)
(return-from found? lst)))))))
我认为使用 loop 而不是 do 使它更具可读性：
(defun found? (index lst occupied width)
(if (< index (1- width))
(loop :for j :from 1 :to 9
:unless (find j occupied :test #'=)
:do (setf (nth index lst) j)
(when (found? (1+ index) ; recursion
lst
(cons j occupied)
width)
(return-from found? lst)))
(loop :for j :from 1 :to 9
:unless (find j occupied :test #'=)
:do (setf (nth index lst) j)
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+
(mapcar #'*
'(1000 100 10 1)
(list (third lst)
(first lst)
(first lst)
(second lst))))))
(when (= lefthnd rghthnd)
(return-from found? lst))))))
由于循环相当复杂，我只想写入和读取一次，
所以把外部条件移到里面：
(defun found? (index lst occupied width)
(loop :for j :from 1 :to 9
:unless (find j occupied :test #'=)
:do (setf (nth index lst) j)
(if (< index (1- width))
(when (found? (1+ index) ; recursion
lst
(cons j occupied)
width)
(return-from found? lst))
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+
(mapcar #'*
'(1000 100 10 1)
(list (third lst)
(first lst)
(first lst)
(second lst))))))
(when (= lefthnd rghthnd)
(return-from found? lst))))))
你有没有看到occupied只是lst的前一个或前两个元素，
反转？我们可以通过
递归。我们实际上需要 return 的递归结果，所以
这是更好的参考透明度。
(defun find! ()
(found? 0 ; initially show the number 1
'() ; initially no numbers found
3)) ; numbers list width is 3
(defun found? (index part width)
(loop :for j :from 1 :to 9
:unless (find j part :test #'=)
:do (if (< index (1- width))
(let ((solution (found? (1+ index) ; recursion
(cons j part)
width)))
(when solution
(return-from found? solution)))
(let* ((full (cons j part))
(lefthnd (* 111 (reduce #'+ full)))
(rghthnd (reduce #'+
(mapcar #'*
'(1000 100 10 1)
(list (third full)
(first full)
(first full)
(second full))))))
(when (= lefthnd rghthnd)
(return-from found? full))))))
index和width现在只用于计数，所以我们只需要一个数字，
我们可以数到零。这也表明我们应该
可能将基本情况移出循环：
(defun find! ()
(found? '() ; initially no numbers found
3)) ; numbers list width is 3
(defun found? (part count)
(if (zerop count)
(let* ((full part) ; just rename to show that the number is complete
(lefthnd (* 111 (reduce #'+ full)))
(rghthnd (reduce #'+
(mapcar #'*
'(1000 100 10 1)
(list (third full)
(first full)
(first full)
(second full))))))
(when (= lefthnd rghthnd)
(return-from found? full)))
(loop :for j :from 1 :to 9
:unless (find j part :test #'=)
:do (let ((solution (found? (cons j part)
(1- count))))
(when solution
(return-from found? solution))))))
我认为这或多或少是你可以做的，如果你把它保持在一个单一的
功能。现在你可能想要分开的一代
来自实际代码的排列。例如有一些功能
在广泛使用的库中处理此类事情 alexandria.
使您的代码工作所需的最少编辑是以下三个小更改（在注释中标记为 ;;;; NB）：
- 不允许您像手术一样修改引用列表的结构。为此，它必须是新分配的。
(defun find! ()
(found? 0 ;; initially point to the number 1
(list 1 2 3) ;; initial list ;;;; NB freshly allocated!
'() ;; initially no numbers found
3 ;; numbers list width is 3
) )
- 您必须更改代码结构（移动 one 闭括号 one 行）到 always 将
j 的 push 撤消为 occupied:
(defun found? (index lst occupied width)
(if (< index (1- width))
(do ( (j 1 (1+ j) ) )
( (> j 9) lst)
(unless (some (lambda (x) (= x j)) occupied)
(setf (nth index lst) j)
(push j occupied)
(if (found? (1+ index) lst occupied width) ;; recursion happens here
lst) ;;;; NB
(setf occupied (remove j occupied)))) ;;;; NB _always_ undo the push
(do ( (j 1 (1+ j) ) )
( (> j 9) lst)
(unless (some (lambda (x) (= x j)) occupied)
(setf (nth index lst) j)
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+
(mapcar
(lambda (x y) (* x y))
'(1000 100 10 1)
(list (third lst) (first lst)
(first lst) (second lst))))))
(if (= lefthnd rghthnd)
(return-from found? lst) ;;;; NB actually return here
'nil))))))
- 你还必须 return 结果，一旦找到（也在上面的代码片段中看到）。
如果您将 return-from 行更改为 打印 结果而不是 return 打印结果，您将得到 all[=其中 81=] 已打印。
如果你想把它们全部放在一个列表中而不是打印出来，你可以通过外科手术将每个结果附加到某个外部范围中定义的列表中（或者 cons 到前面并在如果您愿意，一切都已完成。
或者一般来说，您可以更改此代码以接受 callback 并在找到每个结果时调用它，然后让此回调执行它对它所做的任何事情——打印它，将它附加到外部列表，无论如何。
备注：您的代码通过递归遵循一般的 recursive-backtracking approach, creating three nested loops 结构。实际结果在递归的最深层次计算——并通过手术操作放入lst，对应于j从1到9的最内层循环（同时避免重复）。
这里有很多无关紧要的代码。例如，(if (found? ...) lst) 中的 if 根本不需要，可以用 (found? ...) 代替。我也更喜欢不同的名字——occupied 应该真正命名为 used，lst 应该是 res（对于“结果”），index 是规范命名的只是 i，width 只是 n，等等（命名 是 重要）...但是你确实请求了 最小变化。
此代码逐渐计算结果 lst，作为进入嵌套循环最内层的方式的副作用，最终完全设置。
因此这段代码如下Peter Norvig 的 PAIP Prolog 解释器的示例，它遵循相同的范例。在伪代码中：
let used = []
for a from 1 to 9:
if a not in used:
used += [a]
for b from 1 to 9:
if b not in used:
used += [b]
for c from 1 to 9:
if c not in used and valid(a,b,c):
return [a,b,c] # or:
# print [a,b,c] # or:
# call(callback,[a,b,c]) # etc.
remove b from used
remove a from used
这是您的代码 re-structured，已重命名并简化：
(defun find2 ( &aux (res (list 0 0 0))
(used '()) (n (length res)))
(labels
((f (i)
(do ((d 1 (1+ d))) ; for d from 1 to 9...
((> d 9) 'FAIL) ; FAIL: no solution!
(unless (member d used) ; "d" for "digit"
(setf (nth i res) d) ; res = [A... B... C...]
(cond
((< i (- n 1)) ; outer levels
(setf used (cons d used))
(f (1+ i)) ; recursion! going in...
(setf used (cdr used))) ; and we're out.
(T ; the innermost level!
(let ((left (* 111 (reduce #'+ res)))
(rght (reduce #'+
(mapcar #'* '(1000 100 10 1)
(list (third res) ; C A A B
(first res)
(first res)
(second res))))))
(if (= left rght)
(return-from find2 res))))))))) ; success!
(f 0)))
这现在非常类似于您曾经在问题中使用的 C++ 代码，其中工作函数（此处为 f）也仅接收一个参数，指示嵌套循环的深度级别 -- 对应到正在尝试的数字的索引，-- 其余变量在外部范围内（那里是全局的；这里是包含函数 find2 中的辅助变量）。
顺便说一下，您出于某种原因没有尝试任何 0。
“求数字问题”是这样的：
Find unique decimal digits A, B, C such that
CCC
+ BBB
+ AAA
= CAAB
为了在 Common Lisp 中使用递归来解决它，我编写了以下代码：
(defun find! ()
(found? 0 ;; initially point to the number 1
'(1 2 3) ;; initial list
'() ;; initially no numbers found
3 ;; numbers list width is 3
) )
(defun found? (index lst occupied width)
(if (< index (1- width))
(do ( (j 1 (1+ j) ) )
( (> j 9) lst)
(unless (some (lambda (x) (= x j)) occupied)
(setf (nth index lst) j)
(push j occupied)
(if (found? (1+ index) lst occupied width) ;; recursion happens here
lst
(setf occupied (remove j occupied)))))
(do ( (j 1 (1+ j) ) )
( (> j 9) lst)
(unless (some (lambda (x) (= x j)) occupied)
(setf (nth index lst) j)
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+
(mapcar
(lambda (x y) (* x y))
'(1000 100 10 1)
(list (third lst) (first lst)
(first lst) (second lst))))))
(if (= lefthnd rghthnd)
lst
'nil))))))
传递的结果（lst）是(9 9 9)
预期结果 (lst) 是 (9 8 1)，意思是 A=9、B=8、C=1，因此等式 CCC + BBB + AAA = CAAB 成立，即
111 ; CCC
+ 888 ; BBB
+ 999 ; AAA
= 1998 ; CAAB
我应该更改代码的哪些部分才能得到预期的结果？有人可以修复代码吗？请注意，必须使用递归。只有一行递归就足够了，比如 ;; recursion happens here 注释所在的行。
修复此代码的最少修改是什么？
您似乎可以使用另一种语言解决问题，所以我不会花太多时间谈论所使用的problem/algorithm（您已经知道该怎么做）。但是，由于您正在学习 Common Lisp，我将提供一个典型的 Whosebug 答案，并提供很多您没有要求的建议！
- 修正你的 parentheses/indentation，这将使你的代码更清晰。
- 将您的代码拆分为更多、更小的函数。您正在使用具有多个参数的递归函数解决问题，并且该函数超过二十行。这使得阅读和调试变得非常困难。
- 使用built-in函数：
(some (lambda (x) (= x j)) occupied) == (member j occupied :test #'=)，在那种情况下，它仍然可以在不指定测试的情况下工作（这在技术上是错误的，这两个函数并不return相同的东西，但您只将结果用作布尔值，因此这实际上是同一件事）。 (mapcar (lambda (x y) (* x y)) ...)只是(mapcar #'* ...) 的一种更长的写法
'nil == nil，不用引用。使用()而不是nil来表示空列表（与布尔值相对）也是（可以说）很好的风格，但这确实是一个小问题。
就算法而言，如果您使用更小的函数重写它，我将很乐意提供帮助。目前，它确实难以阅读和理解。
编辑： 我仍然试图花时间重写代码并提出一个更简洁的解决方案。 TL;DR：这是最终结果，对您的代码进行了“最小”修改：
(defun find! ()
(found? 0 (list 1 2 3) () 3))
(defun compute-lefthand (list)
(* 111 (reduce #'+ list)))
(defun compute-righthand (list)
(reduce #'+ (mapcar #'*
'(1000 100 10 1)
(list (third list)
(first list)
(first list)
(second list)))))
(defun check-solution (list)
(when (= (compute-lefthand list)
(compute-righthand list))
list))
(defun try-solution (j index list occupied width)
(unless (member j occupied)
(setf (nth index list) j)
(found? (1+ index)
list
(cons j occupied)
width)))
(defun found? (index lst occupied width)
(if (= index width)
(check-solution lst)
(dotimes (j 10)
(when (try-solution j index lst occupied width)
(return lst)))))
除了我最初回答中已经提到的样式问题之外，您的初始代码还存在不稳定的控制流。很难确定 什么 真的被每个递归调用 return 编辑了，因为 你没有更小的函数，所以它不清楚每个部分的目标是什么，信息如何从递归调用传递到父级，修改了哪些对象等等。 现在，我的代码不是最干净的，我可能不会使用这种策略来解决问题，但我尽量保持与您的初始代码接近。主要区别：
- 我把事情分成更小的功能。这让一切都变得更清晰，最重要的是，更容易测试。每个功能 return 都清楚。例如，如果
check-solutionreturn 表示正确的解决方案，则列表为列表，否则为nil；我使用when而不是if控制结构这一事实清楚地表明了这一点。 - 我把
do换成dotimes也更清楚；正在变化的变量及其在每一步的变化方式现在立即可见。 - 我不使用
do/dotimes宏的&optional return参数，而是使用明确的return。然后可以清楚地确定什么正在returned，以及什么时候。 - 我不使用
push/pop来修改我的列表。您正在使用递归策略，因此您的“修改”应该采用传递给函数的不同参数的形式。再一次，通过准确了解每个函数对每个参数的作用，它使程序推理变得更容易。一个更好的解决方案也是删除对setf的调用，而是使用(cons <smtg> lst)作为递归调用的参数，但这很好。
你的初始程序中的错误可能是因为你的函数并不像你想的那样return，因为你有几个连续的表达式，每个表达式在不同的情况下被调用，return值本身是错误的，因为它们的顺序不正确，并且使用 do 的可选 return 值在错误的时间修改对象和 return 它们。
TL;DR: 把事情分开；让每个函数只做一件事情。
您的代码
(defun find! ()
(found? 0 ;; initially show the number 1
'(1 2 3) ;; initial list
'() ;; initially no numbers found
3 ;; numbers list width is 3
) )
(defun found? (index lst occupied width)
(if (< index (1- width))
(do ( (j 1 (1+ j) ) )
( (> j 9) lst)
(unless (some (lambda (x) (= x j)) occupied)
(setf (nth index lst) j)
(push j occupied)
(if (found? (1+ index) lst occupied width) ;; recursion
lst
(setf occupied (remove j occupied)))))
(do ( (j 1 (1+ j) ) )
( (> j 9) lst)
(unless (some (lambda (x) (= x j)) occupied)
(setf (nth index lst) j)
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+ (mapcar (lambda (x y) (* x y))
'(1000 100 10 1)
(list (third lst) (first lst) (first lst) (second lst))
))))
(if (= lefthnd rghthnd)
lst
'nil))))))
缩进和注释样式：end-of-line注释使用单个分号， 对齐 non-body 个参数，将正文缩进两个空格
(defun find! ()
(found? 0 ; initially show the number 1
'(1 2 3) ; initial list
'() ; initially no numbers found
3)) ; numbers list width is 3
(defun found? (index lst occupied width)
(if (< index (1- width))
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (some (lambda (x) (= x j)) occupied)
(setf (nth index lst) j)
(push j occupied)
(if (found? (1+ index) lst occupied width) ; recursion
lst
(setf occupied (remove j occupied)))))
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (some (lambda (x) (= x j)) occupied)
(setf (nth index lst) j)
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+
(mapcar (lambda (x y) (* x y))
'(1000 100 10 1)
(list (third lst)
(first lst)
(first lst)
(second lst))))))
(if (= lefthnd rghthnd)
lst
'nil))))))
使用更有说服力的谓词：find 或 member。不要将 * 包裹在 lambda 中 没有其他的。 （我会把 find! 放在一边。）
(defun found? (index lst occupied width)
(if (< index (1- width))
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(push j occupied)
(if (found? (1+ index) lst occupied width) ; recursion
lst
(setf occupied (remove j occupied)))))
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+
(mapcar #'*
'(1000 100 10 1)
(list (third lst)
(first lst)
(first lst)
(second lst))))))
(if (= lefthnd rghthnd)
lst
'nil))))))
do 的正文没有 return 任何内容。有很多死代码，
我们现在删除：
(defun found? (index lst occupied width)
(if (< index (1- width))
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(push j occupied)
(unless (found? (1+ index) lst occupied width) ; recursion
(setf occupied (remove j occupied)))))
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)))))
我们可以有条件地推送，而不是推送然后有条件地删除：
(defun found? (index lst occupied width)
(if (< index (1- width))
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(when (found? (1+ index) lst occupied width) ; recursion
(push j occupied))))
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)))))
虽然它在性能上有所不同，但将外部条件 进入内部主体使其在这里更具可读性：
(defun found? (index lst occupied width)
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(when (and (< index (1- width))
(found? (1+ index) lst occupied width)) ; recursion
(push j occupied)))))
除了几次数到 9 之外，这没有任何作用，这似乎是一致的 根据您的发现。
我猜您想 return 从死代码中提取一些东西。你可能
想为此使用 return-from。
(defun found? (index lst occupied width)
(if (< index (1- width))
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(push j occupied)
(if (found? (1+ index) lst occupied width) ; recursion
(return-from found? lst)
(setf occupied (remove j occupied)))))
(do ((j 1 (1+ j)))
((> j 9) lst)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+
(mapcar #'*
'(1000 100 10 1)
(list (third lst)
(first lst)
(first lst)
(second lst))))))
(when (= lefthnd rghthnd)
(return-from found? lst)))))))
这个returns(1 2 9)，这是错误的。问题似乎是你 return 列表即使你 运行 超过 9，但你想 return nil 然后， 因为你没有找到任何东西。
(defun found? (index lst occupied width)
(if (< index (1- width))
(do ((j 1 (1+ j)))
((> j 9) nil) ; <- nothing found
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(push j occupied)
(if (found? (1+ index) lst occupied width) ; recursion
(return-from found? lst)
(setf occupied (remove j occupied)))))
(do ((j 1 (1+ j)))
((> j 9) nil) ; <- nothing found
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+
(mapcar #'*
'(1000 100 10 1)
(list (third lst)
(first lst)
(first lst)
(second lst))))))
(when (= lefthnd rghthnd)
(return-from found? lst)))))))
这个returns(9 8 1)，是正确的。现在我似乎明白了什么 你正在尝试做，让我们再重构一点。而不是推动和 从占用的列表中删除，只需使用新元素创建一个新列表 短暂在前：
(defun found? (index lst occupied width)
(if (< index (1- width))
(do ((j 1 (1+ j)))
((> j 9) nil)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(when (found? (1+ index) ; recursion
lst
(cons j occupied)
width)
(return-from found? lst))))
(do ((j 1 (1+ j)))
((> j 9) nil)
(unless (find j occupied :test #'=)
(setf (nth index lst) j)
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+
(mapcar #'*
'(1000 100 10 1)
(list (third lst)
(first lst)
(first lst)
(second lst))))))
(when (= lefthnd rghthnd)
(return-from found? lst)))))))
我认为使用 loop 而不是 do 使它更具可读性：
(defun found? (index lst occupied width)
(if (< index (1- width))
(loop :for j :from 1 :to 9
:unless (find j occupied :test #'=)
:do (setf (nth index lst) j)
(when (found? (1+ index) ; recursion
lst
(cons j occupied)
width)
(return-from found? lst)))
(loop :for j :from 1 :to 9
:unless (find j occupied :test #'=)
:do (setf (nth index lst) j)
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+
(mapcar #'*
'(1000 100 10 1)
(list (third lst)
(first lst)
(first lst)
(second lst))))))
(when (= lefthnd rghthnd)
(return-from found? lst))))))
由于循环相当复杂，我只想写入和读取一次， 所以把外部条件移到里面：
(defun found? (index lst occupied width)
(loop :for j :from 1 :to 9
:unless (find j occupied :test #'=)
:do (setf (nth index lst) j)
(if (< index (1- width))
(when (found? (1+ index) ; recursion
lst
(cons j occupied)
width)
(return-from found? lst))
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+
(mapcar #'*
'(1000 100 10 1)
(list (third lst)
(first lst)
(first lst)
(second lst))))))
(when (= lefthnd rghthnd)
(return-from found? lst))))))
你有没有看到occupied只是lst的前一个或前两个元素， 反转？我们可以通过 递归。我们实际上需要 return 的递归结果，所以 这是更好的参考透明度。
(defun find! ()
(found? 0 ; initially show the number 1
'() ; initially no numbers found
3)) ; numbers list width is 3
(defun found? (index part width)
(loop :for j :from 1 :to 9
:unless (find j part :test #'=)
:do (if (< index (1- width))
(let ((solution (found? (1+ index) ; recursion
(cons j part)
width)))
(when solution
(return-from found? solution)))
(let* ((full (cons j part))
(lefthnd (* 111 (reduce #'+ full)))
(rghthnd (reduce #'+
(mapcar #'*
'(1000 100 10 1)
(list (third full)
(first full)
(first full)
(second full))))))
(when (= lefthnd rghthnd)
(return-from found? full))))))
index和width现在只用于计数，所以我们只需要一个数字， 我们可以数到零。这也表明我们应该 可能将基本情况移出循环：
(defun find! ()
(found? '() ; initially no numbers found
3)) ; numbers list width is 3
(defun found? (part count)
(if (zerop count)
(let* ((full part) ; just rename to show that the number is complete
(lefthnd (* 111 (reduce #'+ full)))
(rghthnd (reduce #'+
(mapcar #'*
'(1000 100 10 1)
(list (third full)
(first full)
(first full)
(second full))))))
(when (= lefthnd rghthnd)
(return-from found? full)))
(loop :for j :from 1 :to 9
:unless (find j part :test #'=)
:do (let ((solution (found? (cons j part)
(1- count))))
(when solution
(return-from found? solution))))))
我认为这或多或少是你可以做的，如果你把它保持在一个单一的
功能。现在你可能想要分开的一代
来自实际代码的排列。例如有一些功能
在广泛使用的库中处理此类事情 alexandria.
使您的代码工作所需的最少编辑是以下三个小更改（在注释中标记为 ;;;; NB）：
- 不允许您像手术一样修改引用列表的结构。为此，它必须是新分配的。
(defun find! ()
(found? 0 ;; initially point to the number 1
(list 1 2 3) ;; initial list ;;;; NB freshly allocated!
'() ;; initially no numbers found
3 ;; numbers list width is 3
) )
- 您必须更改代码结构（移动 one 闭括号 one 行）到 always 将
j的push撤消为occupied:
(defun found? (index lst occupied width)
(if (< index (1- width))
(do ( (j 1 (1+ j) ) )
( (> j 9) lst)
(unless (some (lambda (x) (= x j)) occupied)
(setf (nth index lst) j)
(push j occupied)
(if (found? (1+ index) lst occupied width) ;; recursion happens here
lst) ;;;; NB
(setf occupied (remove j occupied)))) ;;;; NB _always_ undo the push
(do ( (j 1 (1+ j) ) )
( (> j 9) lst)
(unless (some (lambda (x) (= x j)) occupied)
(setf (nth index lst) j)
(let ((lefthnd (* 111 (reduce #'+ lst)))
(rghthnd (reduce #'+
(mapcar
(lambda (x y) (* x y))
'(1000 100 10 1)
(list (third lst) (first lst)
(first lst) (second lst))))))
(if (= lefthnd rghthnd)
(return-from found? lst) ;;;; NB actually return here
'nil))))))
- 你还必须 return 结果，一旦找到（也在上面的代码片段中看到）。
如果您将 return-from 行更改为 打印 结果而不是 return 打印结果，您将得到 all[=其中 81=] 已打印。
如果你想把它们全部放在一个列表中而不是打印出来，你可以通过外科手术将每个结果附加到某个外部范围中定义的列表中（或者 cons 到前面并在如果您愿意，一切都已完成。
或者一般来说，您可以更改此代码以接受 callback 并在找到每个结果时调用它，然后让此回调执行它对它所做的任何事情——打印它，将它附加到外部列表，无论如何。
备注：您的代码通过递归遵循一般的 recursive-backtracking approach, creating three nested loops 结构。实际结果在递归的最深层次计算——并通过手术操作放入lst，对应于j从1到9的最内层循环（同时避免重复）。
这里有很多无关紧要的代码。例如，(if (found? ...) lst) 中的 if 根本不需要，可以用 (found? ...) 代替。我也更喜欢不同的名字——occupied 应该真正命名为 used，lst 应该是 res（对于“结果”），index 是规范命名的只是 i，width 只是 n，等等（命名 是 重要）...但是你确实请求了 最小变化。
此代码逐渐计算结果 lst，作为进入嵌套循环最内层的方式的副作用，最终完全设置。
因此这段代码如下Peter Norvig 的 PAIP Prolog 解释器的示例，它遵循相同的范例。在伪代码中：
let used = []
for a from 1 to 9:
if a not in used:
used += [a]
for b from 1 to 9:
if b not in used:
used += [b]
for c from 1 to 9:
if c not in used and valid(a,b,c):
return [a,b,c] # or:
# print [a,b,c] # or:
# call(callback,[a,b,c]) # etc.
remove b from used
remove a from used
这是您的代码 re-structured，已重命名并简化：
(defun find2 ( &aux (res (list 0 0 0))
(used '()) (n (length res)))
(labels
((f (i)
(do ((d 1 (1+ d))) ; for d from 1 to 9...
((> d 9) 'FAIL) ; FAIL: no solution!
(unless (member d used) ; "d" for "digit"
(setf (nth i res) d) ; res = [A... B... C...]
(cond
((< i (- n 1)) ; outer levels
(setf used (cons d used))
(f (1+ i)) ; recursion! going in...
(setf used (cdr used))) ; and we're out.
(T ; the innermost level!
(let ((left (* 111 (reduce #'+ res)))
(rght (reduce #'+
(mapcar #'* '(1000 100 10 1)
(list (third res) ; C A A B
(first res)
(first res)
(second res))))))
(if (= left rght)
(return-from find2 res))))))))) ; success!
(f 0)))
这现在非常类似于您曾经在问题中使用的 C++ 代码，其中工作函数（此处为 f）也仅接收一个参数，指示嵌套循环的深度级别 -- 对应到正在尝试的数字的索引，-- 其余变量在外部范围内（那里是全局的；这里是包含函数 find2 中的辅助变量）。
顺便说一下，您出于某种原因没有尝试任何 0。