<jupyter_start><jupyter_text>SICP 习题 （2.43）解题总结：八皇后问题的错误解法 习题2.43说Louis在解2.42题的时候遇到了困难，程序跑起来特别慢，让我们分析原因。先看看他写的代码是什么样的：<jupyter_code>(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
	(list empty-board)
	(filter
	 (lambda (positions) (safe? k positions))
	 (flatmap
	  (lambda (new-row)
	    (map (lambda (rest-of-queens)
		   (adjoin-position new-row k rest-of-queens))
		 (queen-cols (- k 1))))
	  (enumerate-interval 1 board-size)))))
  (queen-cols board-size))<jupyter_output><empty_output><jupyter_text>不仔细看都没看出来和正确的题解有什么不同。下面放上正确的题解：<jupyter_code>(define (queens-right 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))<jupyter_output><empty_output><jupyter_text>题目还特意派出Eva来帮忙，先让Eva看看这个bug，Eva说是因为(flatmap) 和 (map) 的嵌套写反了。那么，这两个函数写反顺序会有什么问题呢。 如果你不运行代码直接看出问题在哪里，那么对Lisp里面的递归和lambda函数理解就比较到位了。这里的关键在于`(queen-cols (- k 1))`被调用多少次。如果一个函数里有行语句不在lambda里，那么函数调用一次这行语句就被执行一次，因为Lisp里没有循环语句! :-)如果像`(queen-cols (- k 1))`这样的递归调用，那就是递归调用几次就执行几次，如果board-size是8，那么按程序定义就是会有8次递归调用。不幸的是，Louis把`(queen-cols (- k 1))`放在lambda里了，放在lambda里就要看lambda被调用了几次。这个lambda函数是对`(enumerate-interval 1 board-size)`执行的map，所以这个lambda会被调用8次，也就是说每次`(queen-cols)`运行都会调用自己8次，可怕的是每次调用自己又会产生8次对自己的递归调用，这个就是指数级的增长了。如果2.42里的正解需要T的时间，那2.43这个错误的解估计要T * 8^8的时间。 下面是完整的代码供测试：<jupyter_code>(define (queens-right 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))

(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
	(list empty-board)
	(filter
	 (lambda (positions) (safe? k positions))
	 (flatmap
	  (lambda (new-row)
	    (map (lambda (rest-of-queens)
		   (adjoin-position new-row k rest-of-queens))
		 (queen-cols (- k 1))))
	  (enumerate-interval 1 board-size)))))
  (queen-cols board-size))





(define empty-board '())

(define (safe? k positions)
  (if (or (same-row (car positions) (cdr positions))
	  (same-45 k (car positions) (cdr positions))
	  (same-135 k (car positions) (cdr positions)))
      #f
      #t))

(define (same-row first-one left-positions)
  (if (null? left-positions)
      #f
      (memq first-one left-positions)) )

(define (same-45 k first-one left-positions)
 
  (if (null? left-positions)
      #f
      (if (< first-one 1)
	  #f
	  (if (= (- first-one 1) (car left-positions))
	      #t
	      (same-45 k (- first-one 1) (cdr left-positions))))))

(define (same-135 k first-one left-positions)
 
  (if (null? left-positions)
      #f
      	  (if (= (+ first-one 1) (car left-positions))
	      #t
	      (same-135 k (+ first-one 1) (cdr left-positions)))))
	      

(define (flat-map-test)
   (flatmap
	  (lambda (rest-of-queens)
	    (map (lambda (new-row)
		   (adjoin-position new-row 1 rest-of-queens))
		 (enumerate-interval 1 9)))
	  queen-cols-1))

 (define queen-cols-1 '((1) (2) (3) (4) (5) (6) (7) (8) (9)))

(define (adjoin-position new-row k rest-of-queens)
  
	 (append  (list new-row) rest-of-queens))

(define (enumerate-interval low high) 
   (if (> low high) 
       '()
       (cons low (enumerate-interval (+ low 1) high)))) 

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
	  (accumulate op initial (cdr sequence)))))

(define (flatmap proc seq)
  (accumulate append '() (map proc seq)))



(define (increase-one x)
  (+ x 1))

(define (increase-list-element list-x)
  (map increase-one list-x))



(define (filter function input-list)
  (if (pair? input-list)
      (if (function (car input-list))
          (cons (car input-list) (filter function (cdr input-list)))
          (filter function (cdr input-list)))
      ()
      ))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.16259966175404686, 'fraction_numerical': 0.01787871466537811, 'mean_word_length': 3.58980044345898, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '646137', 'license': 'MIT', 'n_tokens_mistral': 1963, 'n_tokens_neox': 1925, 'n_words': 349, 'path': 'cn/.ipynb_checkpoints/sicp-2-43-checkpoint.ipynb', 'repo_name': 'DamonDeng/sicp_exercise', 'size': '4139'}