我正在努力解决 SICP 中的 N 皇后问题(这本书；我花了几天时间——最后一个问题: Solving Eight-queens in scheme )。这是我的辅助函数:
#lang sicp
; the SICP language in Racket already defines this:
; (define nil '()
; boilerplate: filter function and range functions
(define (filter func lst)
(cond
((null? lst)
nil)
(else
(if (func (car lst))
(cons (car lst) (filter func (cdr lst)))
(filter func (cdr lst))))))
(define (range a b)
(if (> a b)
nil
(cons a (range (+ 1 a) b))))
; Selectors/handlers to avoid confusion on the (col, row) notation:
; representing it a position as (col, row), using 1-based indexing
(define (make-position col row) (cons col (list row)))
(define (col p) (car p))
(define (row p) (cadr p))
; adding a new position to a board
(define (add-new-position existing-positions p)
(append existing-positions
(list (make-position (col p) (row p)))))
; The 'safe' function
(define (any? l proc)
(cond ((null? l) #f)
((proc (car l)) #t)
(else (any? (cdr l) proc))))
(define (none? l proc) (not (any? l proc)))
(define (safe? existing-positions p)
(let ((bool (lambda (x) x)) (r (row p)) (c (col p)))
(and
; is the row safe? i.e., no other queen occupies that row?
(none? (map (lambda (p) (= (row p) r)) existing-positions)
bool)
; safe from the diagonal going up
(none? (map (lambda (p) (= r (+ (row p) (- c (col p)))))
existing-positions)
bool)
; safe from the diagonal going down
(none? (map (lambda (p) (= r (- (row p) (- c (col p)))))
existing-positions)
bool))))
现在，有了这个样板，我得到的皇后问题的实际/可怕的第一个工作版本:
(define (positions-for-col col size)
(map (lambda (ri) (make-position col ri))
(range 1 size)))
(define (queens board-size)
(define possible-positions '())
(define safe-positions '())
(define all-new-position-lists '())
(define all-positions-list '())
; existing-positions is a LIST of pairs
(define (queen-cols col existing-positions)
(if (> col board-size)
(begin
(set! all-positions-list
(append all-positions-list (list existing-positions))))
(begin
; for the column, generate all possible positions,
; for example (3 1) (3 2) (3 3) ...
(set! possible-positions (positions-for-col col board-size))
; (display "Possible positions: ") (display possible-positions) (newline)
; filter out the positions that are not safe from existing queens
(set! safe-positions
(filter (lambda (pos) (safe? existing-positions pos))
possible-positions))
; (display "Safe positions: ") (display safe-positions) (newline)
(if (null? safe-positions)
; bail if we don't have any safe positions
'()
; otherwise, build a list of positions for each safe possibility
; and recursively call the function for the next column
(begin
(set! all-new-position-lists
(map (lambda (pos)
(add-new-position existing-positions pos))
safe-positions))
; (display "All positions lists: ") (display all-new-position-lists) (newline)
; call itself for the next column
(map (lambda (positions-list) (queen-cols (+ 1 col)
positions-list))
all-new-position-lists))))))
(queen-cols 1 '())
all-positions-list)
(queens 5)
(((1 1) (2 3) (3 5) (4 2) (5 4))
((1 1) (2 4) (3 2) (4 5) (5 3))
((1 2) (2 4) (3 1) (4 3) (5 5))
((1 2) (2 5) (3 3) (4 1) (5 4))
((1 3) (2 1) (3 4) (4 2) (5 5))
说实话，我认为我做了所有 set! 以便我可以更轻松地调试东西(这很常见吗？)我如何删除各种 set!s使其成为正确的功能过程？
作为更新，我能得到的最“简洁”的内容如下，尽管它仍然附加到列表中以构建位置:
(define (queens board-size)
(define all-positions-list '())
(define (queen-cols col existing-positions)
(if (> col board-size)
(begin
(set! all-positions-list
(append all-positions-list
(list existing-positions))))
(map (lambda (positions-list)
(queen-cols (+ 1 col) positions-list))
(map (lambda (pos)
(add-new-position existing-positions pos))
(filter (lambda (pos)
(safe? existing-positions pos))
(positions-for-col col board-size))))))
(queen-cols 1 nil)
all-positions-list)
最后，我认为这是我能做的最好的事情，利用“平面 map ”函数来帮助处理嵌套列表:
; flatmap to help with reduction
(define (reduce function sequence initializer)
(let ((elem (if (null? sequence) nil (car sequence)))
(rest (if (null? sequence) nil (cdr sequence))))
(if (null? sequence)
initializer
(function elem
(reduce function rest initializer)))))
(define (flatmap proc seq)
(reduce append (map proc seq) nil))
; actual
(define (queens board-size)
(define (queen-cols col existing-positions)
(if (> col board-size)
(list existing-positions)
(flatmap
(lambda (positions-list)
(queen-cols (+ 1 col) positions-list))
(map
(lambda (pos)
(add-new-position existing-positions
pos))
(filter
(lambda (pos)
(safe? existing-positions pos))
(positions-for-col col board-size))))))
(queen-cols 1 nil))
与使用 set! 的函数相比，此函数有什么优点吗？或者这更多是一个偏好问题(我发现 set! 更容易阅读和调试)。
最佳答案
当你做SICP题时，如果你努力坚持题目的精神，那将是最有好处的。你可以从上下文中确定精神:书中所涉及的主题、给出的任何帮助代码、使用的术语等。具体来说，避免使用方案语言中尚未介绍的部分；重点不是你能否解决问题，而是你如何解决问题。如果您已获得帮助程序代码，请尝试尽可能地使用它。
SICP 有一种构建复杂性的方法；除非它提出了足够的动机和理由，否则它不会引入一个概念。本书的基本主题是通过抽象进行简化，在这个特定的部分中，您将了解各种高阶过程 - 诸如累加、映射、过滤器、平面映射之类的抽象，它们对序列/列表进行操作，以使您的代码更加结构化、紧凑并最终更易于推理。
正如本节开头所示，您完全可以避免使用此类更高的编程结构，并且仍然可以让程序运行良好，但它们(自由)的使用会导致更加结构化、可读性更高、top- down 样式代码。它与信号处理系统的设计有相似之处，并展示了我们如何从中获得灵感来为我们的代码添加结构:使用映射、过滤器等过程来划分我们的代码逻辑，不仅使其看起来更卫生，而且更方便。可以理解。
如果您过早地使用本书后面才出现的技术，您将错过作者在本节中为您准备的许多关键知识。你需要摆脱以命令式方式思考的冲动。使用套装!在计划中做事并不是一个好方法，直到它成为现实。 SICP 强制您走上一条“困难”的道路，让您以函数式的方式思考，这是有原因的——它是为了让您的思维(和代码)优雅且“干净”。
想象一下，推理生成树递归过程的代码会有多困难，其中每个(子)函数调用都会改变函数的参数。另外，正如我在评论中提到的，赋值给程序员(以及那些阅读代码的人)带来了额外的负担，因为表达式的顺序会影响计算结果，因此更难验证代码执行预期的操作。
编辑:我只是想添加几点，我认为这会增加更多的见解:
- 您的代码使用了 set!没有错(甚至非常不雅)，只是这样做时，你非常明确地告诉你在做什么。除了自下而上之外，迭代还会稍微降低优雅性——通常更难以自下而上地思考。
- 我认为本书的目标之一是教授尽可能递归地做事。你会发现递归是一项至关重要的技术，整本书都不可避免地会用到它。例如，在第 4 章中，您将编写评估器(解释器)，其中作者递归地评估表达式。甚至更早的时候，在 2.3 节中，存在符号微分问题，这也是表达式递归求值的练习。因此，即使您第一次以命令式方式(使用 set!、begin)和自下而上迭代解决了问题，但就问题陈述而言，这不是正确的方式。
话虽如此，这是我解决这个问题的代码(对于 FP 赋予的所有结构和可读性，注释仍然是不可或缺的):
; the board is a list of lists - a physical n x n board, where
; empty positions are 0 and filled positions are 1
(define (queens board-size)
(let ((empty-board (empty-board-gen board-size))) ; minor modification - making empty-board available to queen-cols
(define (queen-cols k)
(if (= k 0)
(list empty-board)
(filter (lambda (positions) (safe? k positions))
; the flatmap below generates a list of new positions
; by 'adjoining position'- adding 'board-size' number
; of new positions for each of the positions obtained
; recursively from (queen-cols (- k 1)), which have
; been found to be safe till column k-1. This new
; set (list) of positions is then filtered using the
; safe? function to filter out unsafe positions
(flatmap
(lambda (rest-of-queens)
; the map below adds 'board-size' number of new
; positions to 'rest-of-queens', which is an
; element of (queen-cols (- k 1))
(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)) ; end of let block
)
; add a column having a queen placed at position (new-row, col).
(define (adjoin-position new-row col rest-queens)
(let ((board-dim (length rest-queens))) ;length of board
; first create a zero 'vector', put a queen in it at position
; 'new-row', then put (replace) this new vector/column at the
; 'col' position in rest-queens
(replace-elem (replace-elem 1 new-row (gen-zero-vector board-dim)) col rest-queens)))
(define (safe? k positions) ; the safe function
(let ((row-pos-k (non-zero-index (item-at-index k positions)))) ; get the row of the queen in column k
(define (iter-check col rem) ;iteratively check if column 'col' of the board is safe wrt the kth column
(let ((rw-col (non-zero-index (car rem)))) ; get the row of 'col' in which a queen is placed
(cond ((= k 1) #t); 1x1 board is always safe
((= col k) #t); if we reached the kth column, we are done
; some simple coordinate geometry
; checks if the row of the queen in col and kth
; column is same, and also checks if the 'slope' of
; the line connecting the queens of the two columns
; is 1 (i.e. if it's a diagonal), if either is true,
; the kth queen is not safe
((or (= row-pos-k rw-col) (= (- k col) (abs (- row-pos-k rw-col)))) #f)
(else (iter-check (+ col 1) (cdr rem)))))) ; check the next column
(iter-check 1 positions))) ; start checking from the first column
; helper functions follow
(define (item-at-index n items) ; given a list, return the nth element
(define (iter idx rem)
(if (= idx n)
(car rem)
(iter (+ idx 1) (cdr rem))))
(iter 1 items))
(define (non-zero-index items)
; gives the first non-zero element from items - used for
; determining the row at which a queen is placed
(define (iter a rem)
(if (> (car rem) 0)
a
(iter (+ a 1) (cdr rem))))
(iter 1 items))
(define (empty-board-gen n) ; the empty board is n lists, each list with n zeros
(map (lambda (x) (map (lambda (y) 0) (enumerate-interval 1 n))) (enumerate-interval 1 n)))
(define (replace-elem new-elem pos items) ; replace item at position pos in items by new-elem, ultimately used for replacing an empty column with a column which has a queen
(define (iter i res rem)
(if (= i pos)
(append res (list new-elem) (cdr rem))
(iter (+ i 1) (append res (list(car rem))) (cdr rem)))) (iter 1 '() items))
(define (gen-zero-vector n) ; generate a list of length n with only zeros as elements
(define (iter a res)
(if (> a n)
res
(iter (+ a 1) (append res (list 0))))) (iter 1 '()))
(define (flatmap proc seq)
(accumulate append '() (map proc seq)))
(define (length items) ; not particularly efficient way for length of a list
(accumulate + 0 (map (lambda (x) 1) items)))
(define (accumulate op null-value seq)
(if (null? seq)
null-value
(op (car seq) (accumulate op null-value (cdr seq)))))
(define (enumerate-interval low high) ; a list of integers from low to hi
(define (iter a b res)
(if (> a b)
res
(iter (+ a 1) b (append res (cons a '())))))
(iter low high '()))
关于functional-programming - 如何消除方案中此函数的可变性(N 皇后)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/67912848/