SketchyLISP Stuff | Copyright (C) 2006 Nils M Holm |
[ More Sketchy LISP Stuff ] |
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)
[ More Sketchy LISP Stuff ] |