;; -*- coding: euc-jp -*- ;; Nqueen ;; n¡ßn ¤Î¸ß¤¤¤Ë¸ú¤Àþ¾å¤Ë¤Ê¤¤¥¯¥¤¡¼¥ó¤ÎÇÛÎó¤ò¤ß¤Ä¤±¤ë ;; SHINYAMA Yusuke (euske@cl.cs.titech.ac.jp) ;; This software is public domain. (define (decr x) (- x 1)) (define (incr x) (+ x 1)) ; rotate: ¥Ù¥¯¥¿ x ¤ò posÍ×ÁÇ ¤À¤±²óž¤µ¤»¤ë (define (rotate x pos) (do ((last (decr (vector-length x))) (x0 (vector-ref x pos)) (i pos (incr i))) ((= i last) (vector-set! x last x0)) (vector-set! x i (vector-ref x (incr i))))) ; rotrec: ¥Ù¥¯¥¿ x ¤ÎÍ×ÁǤΡ¢¤¢¤é¤æ¤ëÇÛÃÖ¤ÎÁȤ߹ç¤ï¤»¤Ë func ¤òŬÍѤ¹¤ë (define (rotrec func x pos) (let ((last (decr (vector-length x)))) (if (= pos last) (func x) (do ((i pos (incr i))) ((< last i) #f) (rotrec func x (incr pos)) (rotate x pos))))) ; genpat: n¡ßn ¤ÎÈפνé´ü¥Ñ¥¿¡¼¥ó¤òºî¤ë (define (genpat n) (let ((x (make-vector n))) (do ((i 0 (incr i))) ((= n i) x) (vector-set! x i i)))) ; checkqueen: ¥Ñ¥¿¡¼¥ó p ¤¬¤¹¤Ù¤Æ¸ß¤¤¤Ë¸ú¤Àþ¾å¤Ë¤Ê¤¤¥¯¥¤¡¼¥ó¤Ê¤é #t (define (checkqueen p) (define (loop i diag0 diag1) ; i ¤Ï¥«¥¦¥ó¥¿, diag0, diag1 ¤Ï¥ê¥¹¥È (or (zero? i) (let* ((x (decr i)) (y (vector-ref p x)) (d0 (+ x y)) (d1 (- x y))) ; (format #t "check: ~a (~a,~a) in ~a,~a\n" p x y diag0 diag1) (and (not (or (memv d0 diag0) (memv d1 diag1))) (loop (decr i) (cons d0 diag0) (cons d1 diag1)))))) (loop (vector-length p) '() '())) ; nqueen: ¥á¥¤¥ó¥ë¡¼¥Á¥ó (define (nqueen n) (let ((result '())) (rotrec (lambda (p) (if (checkqueen p) (set! result (cons (vector->list p) result)))) (genpat n) 0) result)) ; sample ;(display (nqueen 8))(newline)(exit) (define (main args) (display (nqueen 8)) (newline) 0)