;使用到的未定義的函數,屬于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)))