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