[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/BL9RmfPM    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Mar 28:
; n-queens

(define (range . args)
  (case (length args)
    ((1) (range 0 (car args) (if (negative? (car args)) -1 1)))
    ((2) (range (car args) (cadr args) (if (< (car args) (cadr args)) 1 -1)))
    ((3) (let ((le? (if (negative? (caddr args)) >= <=)))
           (let loop ((x(car args)) (xs '()))
             (if (le? (cadr args) x)
                 (reverse xs)
                 (loop (+ x (caddr args)) (cons x xs))))))
    (else (error 'range "unrecognized arguments"))))

(define (safe? row offset board)
  (or (null? board)
      (and (not (= (+ row offset) (car board)))
           (not (= (- row offset) (car board)))
           (safe? row (+ offset 1) (cdr board)))))

(define (queens n)
  (let loop ((qs (range n 0)) (xs '()) (bs '()))
    (if (null? qs)
        (if (pair? xs) '() (list bs))
        (append
          (if (not (safe? (car qs) 1 bs)) '()
            (loop (append (cdr qs) xs) '() (cons (car qs) bs)))
          (loop (cdr qs) (cons (car qs) xs) bs)))))

(display (length (queens 8))) (newline)
(display (queens 5)) (newline)


Output:
1
2
92
((2 4 1 3 5) (3 1 4 2 5) (1 3 5 2 4) (2 5 3 1 4) (5 2 4 1 3) (1 4 2 5 3) (5 3 1 4 2) (4 1 3 5 2) (4 2 5 3 1) (3 5 2 4 1))


Create a new paste based on this one


Comments: