t3x.org / sketchy / prog / queens.html
SketchyLISP Stuff Copyright (C) 2006 Nils M Holm

queens

Conformance: R5RS

Purpose: Solve the N-queens problem using backtracking.
 
NOTICE: this program is SLOW.

Arguments:
N - number of queens.

Implementation:

(define (queens board-size)
  (letrec

    ; Translate square number to column number
    ((column (lambda (x)
      (quotient x board-size)))

    ; Translate square number to row number
    (row (lambda (x)
      (remainder x board-size)))

    ; Can X attack Y horizontally or vertically?
    (can-attack-hv-p (lambda (x y)
      (or (= (row x) (row y))
          (= (column x) (column y)))))

    ; Compute |X-Y|
    (abs-diff (lambda (x y)
      (cond ((< x y) (- y x))
        (#t (- x y)))))

    ; Can X attack Y diagonally?
    (can-attack-dia-p (lambda (x y)
      (= (abs-diff (column x) (column y))
         (abs-diff (row x) (row y)))))

    ; Can X attack Y?
    (can-attack-p (lambda (x y)
      (or (can-attack-hv-p x y)
          (can-attack-dia-p x y))))

    ; Test whether the square X is safe on a board
    ; already containing the pieces listed in B
    (safe-place-p (lambda (x b)
      (cond ((null? b) #t)
        ((can-attack-p (car b) x) #f)
        (#t (safe-place-p x (cdr b))))))

    ; Compute the number of the first square
    ; of the next column, where Q is any square
    ; in the current column
    (next-column (lambda (q)
      (* (quotient (+ q board-size)
                   board-size)
         board-size)))

    ; Solve N Queens:
    ; Q = next square to check
    ; C = current column
    ; B = board so far
    (n-queens (lambda (q c b)
      (cond ((= c board-size) b)
        ((not (= (column q) c))
          (cond ((null? b) '())
            (#t (n-queens (+ 1 (car b))
                          (- c 1)
                          (cdr b)))))
        ((safe-place-p q b)
          (n-queens (next-column q)
                    (+ 1 c)
                    (cons q b)))
        (#t (n-queens (+ 1 q) c b))))))

    (n-queens 0 0 '())))

Example:

(queens 4) 
=> (14 8 7 1)