代码之家 › 专栏 › 技术社区 › J. Mini

为什么我的n-queens代码返回空列表?

sicp lisp scheme

J. Mini · 技术社区 · 4 年前

我目前正在努力 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-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 2 5 (list 10 11 12 13 14 15 16)) 工作得很好,但那 女王 应该叫我所理解的 (adjoin-position 1 1 (list nil)) ,这也给出了一个可用的结果: (1 ()) 我是否误解了参数 女王 正在传递给 邻接位置 ?

我还没有学会如何调试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:(() ())
((()) (() () () ()))

这意味着错误在以下代码块中,但我没有看到它。

(lambda (rest-of-queens)
  (map (lambda (new-row)
         (adjoin-position new-row k rest-of-queens))
       (enumerate-interval 1 board-size)))

我能想到的最远的是 (= depth 1) 分支 邻接位置 s cond 这句话似乎永远不会结束。我不知道为什么,我只知道坚持一个 display 其中的一行显示该分支从未被使用过。看来它 old-solutions 论点正在通过 nil ?

0 回复 | 直到 4 年前

codybartfast 4 年前

首先,让我描述一下我是如何理解这个程序的工作原理的。因为如果我们对它应该如何工作有不同的想法,那么理解它的实现就很难了。

假设我们已经有了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-Column问题,我们从2-Column问题的第一个解决方案开始,然后为皇后可以放置在第三列中的8个可能行生成8个可能的板位置:

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))

通过扩展2列解决方案,将邻接位置调用8次以创建要测试的位置。(一个可能的混淆原因是,邻接位置的前两个参数是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|_|_

正如你所看到的,我的邻接位置与你的完全不同,它需要一个列表列表,并返回一个更长的列表列表(板上皇后的坐标)。

我发现很难理解我自己的解决方案,目前我很难理解你的解决方案是如何运作的。如果我的描述中的图像/算法部分与你的解决方案相匹配,并且只是位置的表示/实现不同,那么如果你能描述一下你是如何表示这些位置的,这可能会很有用。例如,您希望看到什么,而不是:

  (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))
  ...

J. Mini 4 年前

问题是找到bug,问题几乎成功了。在问题中,我们得到了:

看来它 old-solutions 这个论点被否决了吗?

解释这一点,以及所讨论的错误,并不难。所确定的问题是:

这意味着错误在以下代码块中,但我没有看到它。
(lambda (rest-of-queens)
 (map (lambda (new-row)
        (adjoin-position new-row k rest-of-queens))
      (enumerate-interval 1 board-size)))

要了解出了什么问题,我们需要看看 rest-of-queens 争论。相关部分是 其余皇后 将成为 旧的解决方案 我们怀疑的参数。从引用的代码块向上看一层,我们发现传递给 其余皇后 是列表中的条目吗 (queen-cols (- k 1)) (它通过电话传递给 flatmap ,这是一个 map ). 这就是我们的错误所在。这个问题怀疑电话 adjoin-position 是 (adjoin-position 1 1 (list nil)) ,在哪里 (list nil) 本应来自以下电话 (女王科尔斯(-k1)) 最终达到 = n 0 案件。虽然这是正确的 queen-cols 会回来的 (无列表) 并将其传递给 平面图 ,错误忽略了这样一个事实,即因为 平面图 是a 地图 ,论点传递给 邻接位置 是元素 (无列表) 即,所讨论的呼叫具有 nil 作为其最终参数,不是 (无列表) 因此, 邻接位置 只使用它 ((null? to-append-right) to-append-left) 树枝,使其几乎毫无用处。