; name: queens
; purpose: find the solutions for the n queens problem
; synopsis: (queens n)
; language: Scheme
; author: Alejandro Gómez de Argüello y de Laburu
; copyright: © 2006 by Alejandro Gómez de Argüello y de Laburu
; $Revision: 1.9 $
; $Date: 2006/03/12 21:58:39 $

; queens : number -> (listof (listof (number..number)))
; Given a positive number,
; it returns the list of
; lists of zero-indexed board positions for as many queens
; placed on chessboards of as many squares per side
; in such a way that the queens cannot take each other.
(define queens
  (lambda (n)
    (local ((define my-columns (build-list n identity))
            (define my-rows (build-list n identity))
            (define my-ok-position?
              (lambda (column row so-far)
                (or (empty? so-far)
                    (andmap (lambda (a-cons) ; check for diagonal take
                              (not (= (abs (- column (first a-cons)))
                                      (abs (- row (rest a-cons))))))
                            so-far))))
            (define my-queens
              (lambda (so-far columns rows)
                (apply append ; flattening
                       (if (empty? columns) ; done? (assumes n-by-n board)
                           (list (list so-far)); list-in-list -- as below
                           (local ((define my-column (first columns)))
                             (filter cons? ; chuck non-solutions
                                     (map (lambda (a-row)
                                            (and (my-ok-position? my-column a-row so-far)
                                                 (my-queens (cons (cons my-column a-row) so-far)
                                                            (rest columns)
                                                            (remove a-row rows))))
                                          rows))))))))
      (my-queens empty my-columns my-rows))))
(define maximum-number-of-queens 9) ; low n to appease the impatient
; TEST
(define test-queens ; data from http://en.wikipedia.org/wiki/Eight_queens_puzzle
  (lambda ()
    (local ((define number-of-solutions
              '(1 0 0 2 10 4 40 92 352 724 2680 14200 73712 365596 2279184)))
      (andmap (lambda (n)
                (= (length (queens (+ 1 n))) (list-ref number-of-solutions n)))
              (build-list maximum-number-of-queens identity)))))
(define void
  (map (lambda (n)
         (display (string-append "The "
                                 (number->string n)
                                 " queens problem has "
                                 (number->string (length (queens n)))
                                 " solutions\n")))
       (build-list maximum-number-of-queens
                   (lambda (x) (+ 1 x)))))
(time (test-queens))