queens

Language: R5RS Scheme

Purpose: Solve the N-queens problem using backtracking.
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?
       (lambda (x y)
         (or (= (row x) (row y))
             (= (column x) (column y)))))
     ; Compute |X-Y|
     (abs-diff
       (lambda (x y)
         (if (< x y) (- y x)
                     (- x y))))
     ; Can X attack Y diagonally?
     (can-attack-dia?
       (lambda (x y)
         (= (abs-diff (column x) (column y))
            (abs-diff (row x) (row y)))))
     ; Can X attack Y?
     (can-attack?
       (lambda (x y)
         (or (can-attack-hv? x y)
             (can-attack-dia? x y))))
     ; Test whether the square X is safe on a board
     ; already containing the pieces listed in B
     (safe-place?
       (lambda (x b)
         (cond ((null? b) #t)
           ((can-attack? (car b) x) #f)
           (else (safe-place? 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)))
     ; No solution in this column?
     (column-unsolvable?
       (lambda (q c)
         (not (= (column q) c))))
     ; 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)
           ((column-unsolvable? q c)
             (cond ((null? b) '())
               (else (n-queens (+ 1 (car b))
                               (- c 1)
                               (cdr b)))))
           ((safe-place? q b)
             (n-queens (next-column q)
                       (+ 1 c)
                       (cons q b)))
           (else (n-queens (+ 1 q) c b))))))
    (n-queens 0 0 '())))

Example:

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