GaucheでNクイーン

nqueen.scm

#!/usr/local/bin/gosh

(define count 0)

(define (solve? num ls)
  (let loop ((ls ls)(n 1))
    (cond
      ((null? ls)#t)
      ((= (abs (- num (car ls))) n)
       #f)
      (else (loop (cdr ls)(+ n 1))))))

(define (check? lst)
  (let loop ((lst lst))
    (cond
      ((null? (cdr lst))#t)
      ((solve? (car lst) (cdr lst))
       (loop (cdr lst)))
      (else #f))))

(define (queen lst)
  (let loop ((lst lst)(result '()))
    (if (null? lst)
      (and (check? (reverse result))
           (set! count (+ count 1))
           (print (reverse result)))
      (for-each (lambda(x)(loop (delete x lst) (cons x result))) lst)))
  (display count)
  (newline))

(define (main args)
  (display ">> ")(flush)
  (let ((n (read)))
    (queen (iota n 0))))

実行例

.>> 5
(0 2 4 1 3)
(0 3 1 4 2)
(1 3 0 2 4)
(1 4 2 0 3)
(2 0 3 1 4)
(2 4 1 3 0)
(3 0 2 4 1)
(3 1 4 2 0)
(4 1 3 0 2)
(4 2 0 3 1)
10