queen.scm

用scheme实现的八皇后

;使用到的未定义的函数,属于List常用操作模式 

(define (accumulate proc initial sequence)                      ;accumlate 在List各元素上累积运算
  (if (null? sequence) 
      initial 
      (proc (car sequence) 
      (accumulate proc initial (cdr sequence))))) 

(define (flat-map proc seqs)                                    ;flat-map “放平了”,所以称flatmap
  (accumulate append () (map proc seqs))) 

 
(define (enumerate-interval low high)                           ;enumerate-interval 产生顺序递增的list
  (if (> low high) 
      '() 
      (cons low 
        (enumerate-interval (+ low 1) high)))) 

;--------------------------------------------我是分割线------------------------------------------------------------------------------------------------------

;代码部分

;legal函数用于判断皇后放在第k行是否合理
(define (legal? row arrangement)                                     
    (or (= row 1)                                                                          ;第一行无需判断 
    (null? (filter (lambda (first) (check first (car arrangement))) (cdr arrangement)))))  ; 若check函数为true则不合理


;check函数用于判断标号为place1 和 place2 的两个皇后的位置是否合理 
(define (check place1 place2)                                      
  (or(= (abs (- (car place1) (car place2))) 
      (abs (- (cadr place1) (cadr place2))))            ;是否在同一行上?
     (= (car place1) (car place2))))                    ;是否在同一列上?
 

;如果放在坐标为(x,y)是安全的 则加入结果set中
(define (join y x set)              
  (cons (list y x)set))                                    ;set中是(y x) 对应皇后的列和行 
 

;(compute chessboard)返回结果,第i个元素代表第i种结果,每个结果的第j成员代表这个结果中第j行皇后的所在列,递归地进行判断。 
(define (compute chessboard) 
  (define (computerow k)                                    ;参数k 调用时赋予初值 比如解决八皇后问题时k=8
    (if (= k 0)                                             ;若k=0 说明已经递归到最底层 有解
        (list '())                                          
        (filter (lambda (arrangement) (legal? k arrangement))   ;filter函数用于过滤所有不满足legal条件的 即不合法的放法            
         (flat-map  
          (lambda (set) 
            (map (lambda (y) (join y k set))                ;把所有k行中的每一列都加入left中     
                 (enumerate-interval 1 chessboard)))          
          (computerow (- k 1))))))                          ;递归地对k-1行进行相同处理
  (computerow chessboard)) 
 

;输出结果的编号i
(define(shownumber i)                                   
  (begin (display "No.")(display i)(display " solution:") (newline)))


;根据(car line)的值选择输出 与C中的switch语句功能一样
(define (show line)                                      
          (cond ((= (car line) 1) (begin (display "(Q * * * * * * *)") (newline))) 
                ((= (car line) 2) (begin (display "(* Q * * * * * *)") (newline))) 
                ((= (car line) 3) (begin (display "(* * Q * * * * *)") (newline))) 
                ((= (car line) 4) (begin (display "(* * * Q * * * *)") (newline))) 
                ((= (car line) 5) (begin (display "(* * * * Q * * *)") (newline))) 
                ((= (car line) 6) (begin (display "(* * * * * Q * *)") (newline))) 
                ((= (car line) 7) (begin (display "(* * * * * * Q *)") (newline))) 
                ((= (car line) 8) (begin (display "(* * * * * * * Q)") (newline))) 
                 )) 

  
;输出结果 结果中的第i个元素的值是j 表示的是皇后的坐标为(i,j)
(define(output result)                              
  (cond((null? result)  (newline))     
        ( else(show (car result))             
              (output (cdr result)))))               ;尾递归 迭代输出
 

;resultset表示结果集 通过调用output函数输出所有结果 每次取出结果集中的第一个放入firstset中进行输出
(define(outputset resultset)  
  (let((firstset (car resultset)) (leftset (cdr resultset)))
  (cond((null? resultset) (newline)(display "There are totally ")(display (- 92 (length resultset)))(display " kinds of arrangements.")) 
       (else (shownumber (- 93 (length resultset))) (output firstset) (outputset leftset)))))


;运行时只需调用queens函数即可 参数boardsize表示棋盘大小为boardsize×boardsize
(define (queens boardsize)                           
  (outputset  (compute boardsize)))