ikarus/benchmarks/rnrs-benchmarks/nqueens.ss

41 lines
1.0 KiB
Scheme

;;; NQUEENS -- Compute number of solutions to 8-queens problem.
(library (rnrs-benchmarks nqueens)
(export main)
(import (rnrs) (rnrs-benchmarks))
(define trace? #f)
(define (nqueens n)
(define (_1-to n)
(let loop ((i n) (l '()))
(if (= i 0) l (loop (- i 1) (cons i l)))))
(define (my-try x y z)
(if (null? x)
(if (null? y)
(begin (if trace? (begin (write z) (newline))) 1)
0)
(+ (if (ok? (car x) 1 z)
(my-try (append (cdr x) y) '() (cons (car x) z))
0)
(my-try (cdr x) (cons (car x) y) z))))
(define (ok? row dist placed)
(if (null? placed)
#t
(and (not (= (car placed) (+ row dist)))
(not (= (car placed) (- row dist)))
(ok? row (+ dist 1) (cdr placed)))))
(my-try (_1-to n) '() '()))
(define (main)
(run-benchmark
"nqueens"
nqueens-iters
(lambda (result) (equal? result 92))
(lambda (n) (lambda () (nqueens n)))
8)))