为什么我的 n-queens 代码 return 是空列表？
Why does my n-queens code return empty lists?
我目前正在处理 SICP Exercise 2.42。我知道我的 adjoin-position 函数有问题，因为当我用
替换它时
(define (adjoin-position-WORKING new-row k rest-of-queens)
(cons (list new-row k) rest-of-queens))
我从 queens 得到合理的输出。
在此替换之前，我使用练习模板的代码如下：
#lang sicp
;;Boilerplate functions that the exercise calls:
(define (filter predicate sequence)
(cond ((null? sequence) nil)
((predicate (car sequence))
(cons (car sequence)
(filter predicate (cdr sequence))))
(else (filter predicate (cdr sequence)))))
(define (enumerate-interval low high)
(cond ((> low high) nil)
((= low high) (list high))
(else (cons low (enumerate-interval (+ 1 low) high)))))
(define (flatmap proc seq)
(accumulate append nil (map proc seq)))
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
;;;Start of solution:
(define empty-board nil)
;Placeholder, stops the filter from actually filtering anything:
(define (safe? new-queen-col-numb old-solutions) #t)
;;THE RELEVANT BIT
(define (adjoin-position ultimate-row-index new-queen-col-pos old-solutions)
(define (iter to-append-left to-append-right depth)
(cond ((null? to-append-right) to-append-left)
((= depth 1)
(append to-append-left (cons new-queen-col-pos to-append-right)))
(else (iter (append to-append-left (list (car to-append-right)))
(cdr old-solutions)
(- depth 1)))))
(iter nil old-solutions ultimate-row-index))
;;The template provided by the exercise, untouched by me:
(define (queens board-size)
(define (queen-cols k)
(if (= k 0)
(list empty-board)
(filter
(lambda (positions) (safe? k positions))
(flatmap
(lambda (rest-of-queens)
(map (lambda (new-row)
(adjoin-position new-row k rest-of-queens))
(enumerate-interval 1 board-size)))
(queen-cols (- k 1))))))
(queen-cols board-size))
;;Example of adjoin-position working as expected:
(adjoin-position 2 5 (list 10 11 12 13 14 15 16))
;Output: (10 5 11 12 13 14 15 16)
;i.e. it placed 5 at position 2, as I wanted it to.
;;Code to show that my adjoin-position is bugged.
(map queens (enumerate-interval 1 3))
我的最终函数 (map queens (enumerate-interval 1 3)) 的输出很恐怖：
((())
(() () () ())
(()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()))
将adjoin-position换成adjoin-position-WORKING后，我的输出就可以接受很多了：
((((1 1)))
(((1 2) (1 1)) ((2 2) (1 1)) ((1 2) (2 1)) ((2 2) (2 1)))
(((1 3) (1 2) (1 1))
((2 3) (1 2) (1 1))
((3 3) (1 2) (1 1))
((1 3) (2 2) (1 1))
((2 3) (2 2) (1 1))
((3 3) (2 2) (1 1))
((1 3) (3 2) (1 1))
((2 3) (3 2) (1 1))
((3 3) (3 2) (1 1))
((1 3) (1 2) (2 1))
((2 3) (1 2) (2 1))
((3 3) (1 2) (2 1))
((1 3) (2 2) (2 1))
((2 3) (2 2) (2 1))
((3 3) (2 2) (2 1))
((1 3) (3 2) (2 1))
((2 3) (3 2) (2 1))
((3 3) (3 2) (2 1))
((1 3) (1 2) (3 1))
((2 3) (1 2) (3 1))
((3 3) (1 2) (3 1))
((1 3) (2 2) (3 1))
((2 3) (2 2) (3 1))
((3 3) (2 2) (3 1))
((1 3) (3 2) (3 1))
((2 3) (3 2) (3 1))
((3 3) (3 2) (3 1))))
所以，现在我们确定原来的 adjoin-position 被窃听并返回了一个空列表列表而不是任何包括数字的列表，我留下了我真正的问题 - 原来的 adjoin-position 出错了吗？对我来说最大的惊喜不仅是 (adjoin-position 2 5 (list 10 11 12 13 14 15 16)) 工作得很好，而且 queens 应该调用我理解的 (adjoin-position 1 1 (list nil))，这也给出了一个可用的结果：(1 ()).我是否误解了 queens 传递给 adjoin-position 的参数？
我还没有学会如何调试 Scheme 代码，但是将对 (map (lambda (new-row)... 的调用替换为对 map-debug 的调用：
(define (map-debug proc seq)
(display "Input list: ")
(display seq)
(newline)
(display "Output list:")
(display (map proc seq))
(newline)
(map proc seq))
为 (map queens (enumerate-interval 1 2))
生成以下输出
Input list: (1)
Output list:(())
Input list: (1 2)
Output list:(() ())
Input list: (1 2)
Output list:(() ())
Input list: (1 2)
Output list:(() ())
((()) (() () () ()))
言下之意是bug在下面的代码块中，但是我没看到。
(lambda (rest-of-queens)
(map (lambda (new-row)
(adjoin-position new-row k rest-of-queens))
(enumerate-interval 1 board-size)))
我最清楚的是 adjoin-position 的 cond 声明的 (= depth 1) 分支似乎从来没有 运行。我不知道为什么，我只知道在其中粘贴 display 行表明该分支从未使用过。似乎正在传递其 old-solutions 参数 nil?
首先让我描述一下我是如何理解该程序的工作原理的。因为如果我们对它应该如何工作有不同的想法，那么理解实现就很困难。
假设我们已经有了 1 列和 2 列问题的第一个解决方案：
First of 8 Solutions To the 1-Column Problem:
=============================================
_
|_|
|_|
|_|
|_|
|_|
|_|
|_|
|Q|
position: ((1 1))
First of 42 Solutions To the 2-Column Problem:
==============================================
_ _
|_|_|
|_|_|
|_|_|
|_|_|
|_|_|
|_|Q|
|_|_|
|Q|_|
position: ((2 3) (1 1))
对于 3 列问题，我们从 2 列问题的第一个解决方案开始，然后生成 8 个可能的行的 8 个可能的棋盘位置，皇后可以放置在第 3 列中：
First 8 Positions to Test as Possible Solutions To the 3-Column Problem:
========================================================================
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
|_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|?
|_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|? |_|_|_
|_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|? |_|_|_ |_|_|_
|_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|? |_|_|_ |_|_|_ |_|_|_
|_|_|_ |_|_|_ |_|_|_ |_|_|? |_|_|_ |_|_|_ |_|_|_ |_|_|_
|_|Q|_ |_|Q|_ |_|Q|? |_|Q|_ |_|Q|_ |_|Q|_ |_|Q|_ |_|Q|_
|_|_|_ |_|_|? |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_
|Q|_|? |Q|_|_ |Q|_|_ |Q|_|_ |Q|_|_ |Q|_|_ |Q|_|_ |Q|_|_
First 8 positions to test:
((3 1) (2 3) (1 1))
((3 2) (2 3) (1 1))
((3 3) (2 3) (1 1))
((3 4) (2 3) (1 1))
((3 5) (2 3) (1 1))
((3 6) (2 3) (1 1))
((3 7) (2 3) (1 1))
((3 8) (2 3) (1 1))
Adjoin-position 被调用 8 次以通过扩展 2 列解决方案创建要测试的位置。 （造成混淆的一个可能原因是 adjoin-position 的前两个参数是 row 然后是 col，但通常位置是 col 然后是 row）。
Creating the first 8 positions to test:
(adjoin-position 1 3 ((2 3) (1 1))) => ((3 1) (2 3) (1 1))
(adjoin-position 2 3 ((2 3) (1 1))) => ((3 2) (2 3) (1 1))
(adjoin-position 3 3 ((2 3) (1 1))) => ((3 3) (2 3) (1 1))
(adjoin-position 4 3 ((2 3) (1 1))) => ((3 4) (2 3) (1 1))
(adjoin-position 5 3 ((2 3) (1 1))) => ((3 5) (2 3) (1 1))
(adjoin-position 6 3 ((2 3) (1 1))) => ((3 6) (2 3) (1 1))
(adjoin-position 7 3 ((2 3) (1 1))) => ((3 7) (2 3) (1 1))
(adjoin-position 8 3 ((2 3) (1 1))) => ((3 8) (2 3) (1 1))
然后对这些进行过滤，给出扩展第一个 2 列解决方案的 3 列问题的四个解决方案。
First 4 (of 140) Solutions to the 3-Column problem:
===================================================
positions:
((3 5) (2 3) (1 1))
((3 6) (2 3) (1 1))
((3 7) (2 3) (1 1))
((3 8) (2 3) (1 1))
_ _ _ _ _ _ _ _ _ _ _ _
|_|_|_ |_|_|_ |_|_|_ |_|_|Q
|_|_|_ |_|_|_ |_|_|Q |_|_|_
|_|_|_ |_|_|Q |_|_|_ |_|_|_
|_|_|Q |_|_|_ |_|_|_ |_|_|_
|_|_|_ |_|_|_ |_|_|_ |_|_|_
|_|Q|_ |_|Q|_ |_|Q|_ |_|Q|_
|_|_|_ |_|_|_ |_|_|_ |_|_|_
|Q|_|_ |Q|_|_ |Q|_|_ |Q|_|_
如您所见，我的相邻位置与您的完全不同，它需要一个列表列表和 returns 更长的列表列表（棋盘上皇后的坐标）。
我发现很难理解我自己的解决方案，而目前我正在努力理解您的解决方案。如果我描述的 pictorial/algorithmic 部分与您的解决方案相匹配，并且只有 representation/implementation 的位置不同，那么如果您能描述您如何表示这些位置可能会很有用。例如，您希望看到什么而不是：
(adjoin-position 1 3 ((2 3) (1 1))) => ((3 1) (2 3) (1 1))
(adjoin-position 2 3 ((2 3) (1 1))) => ((3 2) (2 3) (1 1))
(adjoin-position 3 3 ((2 3) (1 1))) => ((3 3) (2 3) (1 1))
...
题目是找bug，题差点就成功了。在问题中，我们得到了：
It appears that its old-solutions argument is being passed nil?
解释这一点以及相关错误并不难。确定的问题：
The implication is that the bug is in the following block of code, but I do not see it.
(lambda (rest-of-queens)
(map (lambda (new-row)
(adjoin-position new-row k rest-of-queens))
(enumerate-interval 1 board-size)))
要了解问题出在哪里，我们需要查看 rest-of-queens 参数。相关部分是 rest-of-queens 将成为我们怀疑的 old-solutions 参数。从引用的代码块往上看一层，我们发现传递给 rest-of-queens 的值是列表 (queen-cols (- k 1)) 中的条目（它是通过调用 flatmap 传递的，它是map）。这就是我们的错误所在。该问题怀疑对 adjoin-position 的调用是 (adjoin-position 1 1 (list nil))，其中 (list nil) 可能来自对 (queen-cols (- k 1)) 的调用，最终到达 = n 0 案例。虽然 queen-cols 将 return (list nil) 传递给 flatmap 是正确的，但错误忽略了一个事实，因为 flatmap 是 [=18] =]，传递给 adjoin-position 的参数是 (list nil) 的元素，即有问题的调用将 nil 作为其最终参数，而不是 (list nil)。因此，adjoin-position 只使用它的 ((null? to-append-right) to-append-left) 分支，这使得它几乎没有用。
我目前正在处理 SICP Exercise 2.42。我知道我的 adjoin-position 函数有问题，因为当我用
(define (adjoin-position-WORKING new-row k rest-of-queens)
(cons (list new-row k) rest-of-queens))
我从 queens 得到合理的输出。
在此替换之前，我使用练习模板的代码如下：
#lang sicp
;;Boilerplate functions that the exercise calls:
(define (filter predicate sequence)
(cond ((null? sequence) nil)
((predicate (car sequence))
(cons (car sequence)
(filter predicate (cdr sequence))))
(else (filter predicate (cdr sequence)))))
(define (enumerate-interval low high)
(cond ((> low high) nil)
((= low high) (list high))
(else (cons low (enumerate-interval (+ 1 low) high)))))
(define (flatmap proc seq)
(accumulate append nil (map proc seq)))
(define (accumulate op initial sequence)
(if (null? sequence)
initial
(op (car sequence)
(accumulate op initial (cdr sequence)))))
;;;Start of solution:
(define empty-board nil)
;Placeholder, stops the filter from actually filtering anything:
(define (safe? new-queen-col-numb old-solutions) #t)
;;THE RELEVANT BIT
(define (adjoin-position ultimate-row-index new-queen-col-pos old-solutions)
(define (iter to-append-left to-append-right depth)
(cond ((null? to-append-right) to-append-left)
((= depth 1)
(append to-append-left (cons new-queen-col-pos to-append-right)))
(else (iter (append to-append-left (list (car to-append-right)))
(cdr old-solutions)
(- depth 1)))))
(iter nil old-solutions ultimate-row-index))
;;The template provided by the exercise, untouched by me:
(define (queens board-size)
(define (queen-cols k)
(if (= k 0)
(list empty-board)
(filter
(lambda (positions) (safe? k positions))
(flatmap
(lambda (rest-of-queens)
(map (lambda (new-row)
(adjoin-position new-row k rest-of-queens))
(enumerate-interval 1 board-size)))
(queen-cols (- k 1))))))
(queen-cols board-size))
;;Example of adjoin-position working as expected:
(adjoin-position 2 5 (list 10 11 12 13 14 15 16))
;Output: (10 5 11 12 13 14 15 16)
;i.e. it placed 5 at position 2, as I wanted it to.
;;Code to show that my adjoin-position is bugged.
(map queens (enumerate-interval 1 3))
我的最终函数 (map queens (enumerate-interval 1 3)) 的输出很恐怖：
((())
(() () () ())
(()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()
()))
将adjoin-position换成adjoin-position-WORKING后，我的输出就可以接受很多了：
((((1 1)))
(((1 2) (1 1)) ((2 2) (1 1)) ((1 2) (2 1)) ((2 2) (2 1)))
(((1 3) (1 2) (1 1))
((2 3) (1 2) (1 1))
((3 3) (1 2) (1 1))
((1 3) (2 2) (1 1))
((2 3) (2 2) (1 1))
((3 3) (2 2) (1 1))
((1 3) (3 2) (1 1))
((2 3) (3 2) (1 1))
((3 3) (3 2) (1 1))
((1 3) (1 2) (2 1))
((2 3) (1 2) (2 1))
((3 3) (1 2) (2 1))
((1 3) (2 2) (2 1))
((2 3) (2 2) (2 1))
((3 3) (2 2) (2 1))
((1 3) (3 2) (2 1))
((2 3) (3 2) (2 1))
((3 3) (3 2) (2 1))
((1 3) (1 2) (3 1))
((2 3) (1 2) (3 1))
((3 3) (1 2) (3 1))
((1 3) (2 2) (3 1))
((2 3) (2 2) (3 1))
((3 3) (2 2) (3 1))
((1 3) (3 2) (3 1))
((2 3) (3 2) (3 1))
((3 3) (3 2) (3 1))))
所以，现在我们确定原来的 adjoin-position 被窃听并返回了一个空列表列表而不是任何包括数字的列表，我留下了我真正的问题 - 原来的 adjoin-position 出错了吗？对我来说最大的惊喜不仅是 (adjoin-position 2 5 (list 10 11 12 13 14 15 16)) 工作得很好，而且 queens 应该调用我理解的 (adjoin-position 1 1 (list nil))，这也给出了一个可用的结果：(1 ()).我是否误解了 queens 传递给 adjoin-position 的参数？
我还没有学会如何调试 Scheme 代码，但是将对 (map (lambda (new-row)... 的调用替换为对 map-debug 的调用：
(define (map-debug proc seq)
(display "Input list: ")
(display seq)
(newline)
(display "Output list:")
(display (map proc seq))
(newline)
(map proc seq))
为 (map queens (enumerate-interval 1 2))
Input list: (1)
Output list:(())
Input list: (1 2)
Output list:(() ())
Input list: (1 2)
Output list:(() ())
Input list: (1 2)
Output list:(() ())
((()) (() () () ()))
言下之意是bug在下面的代码块中，但是我没看到。
(lambda (rest-of-queens)
(map (lambda (new-row)
(adjoin-position new-row k rest-of-queens))
(enumerate-interval 1 board-size)))
我最清楚的是 adjoin-position 的 cond 声明的 (= depth 1) 分支似乎从来没有 运行。我不知道为什么，我只知道在其中粘贴 display 行表明该分支从未使用过。似乎正在传递其 old-solutions 参数 nil?
首先让我描述一下我是如何理解该程序的工作原理的。因为如果我们对它应该如何工作有不同的想法，那么理解实现就很困难。
假设我们已经有了 1 列和 2 列问题的第一个解决方案：
First of 8 Solutions To the 1-Column Problem:
=============================================
_
|_|
|_|
|_|
|_|
|_|
|_|
|_|
|Q|
position: ((1 1))
First of 42 Solutions To the 2-Column Problem:
==============================================
_ _
|_|_|
|_|_|
|_|_|
|_|_|
|_|_|
|_|Q|
|_|_|
|Q|_|
position: ((2 3) (1 1))
对于 3 列问题，我们从 2 列问题的第一个解决方案开始，然后生成 8 个可能的行的 8 个可能的棋盘位置，皇后可以放置在第 3 列中：
First 8 Positions to Test as Possible Solutions To the 3-Column Problem:
========================================================================
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
|_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|?
|_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|? |_|_|_
|_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|? |_|_|_ |_|_|_
|_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|? |_|_|_ |_|_|_ |_|_|_
|_|_|_ |_|_|_ |_|_|_ |_|_|? |_|_|_ |_|_|_ |_|_|_ |_|_|_
|_|Q|_ |_|Q|_ |_|Q|? |_|Q|_ |_|Q|_ |_|Q|_ |_|Q|_ |_|Q|_
|_|_|_ |_|_|? |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_ |_|_|_
|Q|_|? |Q|_|_ |Q|_|_ |Q|_|_ |Q|_|_ |Q|_|_ |Q|_|_ |Q|_|_
First 8 positions to test:
((3 1) (2 3) (1 1))
((3 2) (2 3) (1 1))
((3 3) (2 3) (1 1))
((3 4) (2 3) (1 1))
((3 5) (2 3) (1 1))
((3 6) (2 3) (1 1))
((3 7) (2 3) (1 1))
((3 8) (2 3) (1 1))
Adjoin-position 被调用 8 次以通过扩展 2 列解决方案创建要测试的位置。 （造成混淆的一个可能原因是 adjoin-position 的前两个参数是 row 然后是 col，但通常位置是 col 然后是 row）。
Creating the first 8 positions to test:
(adjoin-position 1 3 ((2 3) (1 1))) => ((3 1) (2 3) (1 1))
(adjoin-position 2 3 ((2 3) (1 1))) => ((3 2) (2 3) (1 1))
(adjoin-position 3 3 ((2 3) (1 1))) => ((3 3) (2 3) (1 1))
(adjoin-position 4 3 ((2 3) (1 1))) => ((3 4) (2 3) (1 1))
(adjoin-position 5 3 ((2 3) (1 1))) => ((3 5) (2 3) (1 1))
(adjoin-position 6 3 ((2 3) (1 1))) => ((3 6) (2 3) (1 1))
(adjoin-position 7 3 ((2 3) (1 1))) => ((3 7) (2 3) (1 1))
(adjoin-position 8 3 ((2 3) (1 1))) => ((3 8) (2 3) (1 1))
然后对这些进行过滤，给出扩展第一个 2 列解决方案的 3 列问题的四个解决方案。
First 4 (of 140) Solutions to the 3-Column problem:
===================================================
positions:
((3 5) (2 3) (1 1))
((3 6) (2 3) (1 1))
((3 7) (2 3) (1 1))
((3 8) (2 3) (1 1))
_ _ _ _ _ _ _ _ _ _ _ _
|_|_|_ |_|_|_ |_|_|_ |_|_|Q
|_|_|_ |_|_|_ |_|_|Q |_|_|_
|_|_|_ |_|_|Q |_|_|_ |_|_|_
|_|_|Q |_|_|_ |_|_|_ |_|_|_
|_|_|_ |_|_|_ |_|_|_ |_|_|_
|_|Q|_ |_|Q|_ |_|Q|_ |_|Q|_
|_|_|_ |_|_|_ |_|_|_ |_|_|_
|Q|_|_ |Q|_|_ |Q|_|_ |Q|_|_
如您所见，我的相邻位置与您的完全不同，它需要一个列表列表和 returns 更长的列表列表（棋盘上皇后的坐标）。
我发现很难理解我自己的解决方案，而目前我正在努力理解您的解决方案。如果我描述的 pictorial/algorithmic 部分与您的解决方案相匹配，并且只有 representation/implementation 的位置不同，那么如果您能描述您如何表示这些位置可能会很有用。例如，您希望看到什么而不是：
(adjoin-position 1 3 ((2 3) (1 1))) => ((3 1) (2 3) (1 1))
(adjoin-position 2 3 ((2 3) (1 1))) => ((3 2) (2 3) (1 1))
(adjoin-position 3 3 ((2 3) (1 1))) => ((3 3) (2 3) (1 1))
...
题目是找bug，题差点就成功了。在问题中，我们得到了：
It appears that its
old-solutionsargument is being passed nil?
解释这一点以及相关错误并不难。确定的问题：
The implication is that the bug is in the following block of code, but I do not see it.
(lambda (rest-of-queens) (map (lambda (new-row) (adjoin-position new-row k rest-of-queens)) (enumerate-interval 1 board-size)))
要了解问题出在哪里，我们需要查看 rest-of-queens 参数。相关部分是 rest-of-queens 将成为我们怀疑的 old-solutions 参数。从引用的代码块往上看一层，我们发现传递给 rest-of-queens 的值是列表 (queen-cols (- k 1)) 中的条目（它是通过调用 flatmap 传递的，它是map）。这就是我们的错误所在。该问题怀疑对 adjoin-position 的调用是 (adjoin-position 1 1 (list nil))，其中 (list nil) 可能来自对 (queen-cols (- k 1)) 的调用，最终到达 = n 0 案例。虽然 queen-cols 将 return (list nil) 传递给 flatmap 是正确的，但错误忽略了一个事实，因为 flatmap 是 [=18] =]，传递给 adjoin-position 的参数是 (list nil) 的元素，即有问题的调用将 nil 作为其最终参数，而不是 (list nil)。因此，adjoin-position 只使用它的 ((null? to-append-right) to-append-left) 分支，这使得它几乎没有用。