queens_function.scm

在plt schenme 下用scheme函数式程序语言所写的八皇后问题

(display "此程序是函数式的N皇后问题")
(define (accumulate op initial sequence);累积函数
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))
 
(define (filter predicate sequence);对sequence中的元素依据predicate进行筛选
  (cond ((null? sequence) '())
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))
 

 
(define (tiaozheng tiao);对数据中的元素进行集合的“并”，如：((1) (2))->(1 2)
  (accumulate append '() tiao))

 (define (enumerate-interval low high);产生一个递增序列：如（1 2 3）
  (if (> low high)
      '()
      (cons low (enumerate-interval (+ low 1) high))))
 

 
(define (v array k)(cond((= 1 k) (car array) );查看array数组中的第k个元素
                        (else (v (cdr array) (- k 1)))
                        ))
 


(define (s array k x) (cond ((= 1 k) (cons x (cdr array)));把array数组中的第k个元素设为x
                            (else (cons (car array) (s (cdr array) (- k 1) x)))
                            ))
 


(define (safe k positions);棋盘中的第k列的摆设是否合法
                     (define(panduan count)
                      (cond((= k count) #t)
                           ((and
                             (not (= (- (v positions count) (v positions k)) (- count k)))
                             (not (= (- (v positions count) (v positions k)) (- k count)))
                             (not (= (v positions count) (v positions k)))
                             (panduan (+ count 1)))
                             #t)
                           (else #f)
                      ))
                     (panduan 1)
                     )
  
(define (adjoin-position new-row k rest-of-queens);在第new-row行k列放置棋子
  (s rest-of-queens k new-row)
  )





(define (queens board-size);产生8皇后的函数
  (begin
   (define empty-board (list (enumerate-interval 1 board-size)))
   
   (define outcount 1)
   
  (define (print ar);对ar表示的棋盘进行打印操作
  
    (define (output ar count);对ar表示的棋盘进行打印操作，count表示打印的是第几个解
    (if (= 0 count)
        (begin
          (newline)
          (display "This is answer ")
          (write outcount)
          (newline)
          (set! outcount (+ 1 outcount))
          )
        (begin
          (newline)
          (map(lambda(t)
               (if(= count t)
                  (display "|Q")
                  (display "|*")))
          ar)
          (output ar (- count 1))
          )
     ))
  (output ar board-size)
  )
  
  
  (define (queen-cols k)  ;在第k列尝试放置合法的棋子
    (if (= k 0)
        empty-board
        (filter
         (lambda (positions) (safe k positions))
         (tiaozheng(map
          (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)))))))
  
  (define (printf arrr);对包含了所有八皇后解的集合进行棋盘的一一输出
    (if (null? arrr)
    (display "OK!")
    (begin (print (car arrr))
           (printf (cdr arrr))
     ))
    )
  
  (printf (queen-cols board-size))
  )
  )