# Rcjp's Weblog

## July 28, 2006

### Queens Chess problem

Filed under: lisp — rcjp @ 1:49 pm

``` ;;; ;;; How to place 8 queens on a chess board so that none attack the others ;;; ;;; find-queens is a recursive implementation ;;; return-queens collects the solutions and uses loop instead of dotimes ;;; ;;; (length (return-queens)) => 92 (proclaim '(optimize (speed 0) (space 0) (debug 3))) (defstruct (square (:print-function (lambda (sq stream depth) (declare (ignore depth)) (format stream "(~A, ~A)" (square-col sq) (square-row sq))))) (col 1 :type integer) (row 1 :type integer)) (defun print-square (sq stream depth) (declare (ignore depth)) (format stream " (~A, ~A) " (square-col sq) (square-row sq))) (defun find-queens (&optional (queens '())) (let ((col (list-length queens))) (if (= col 8) (format t "~A~%" queens) (dotimes (row 8) (let ((q (make-square :col (+ col 1) :row (+ row 1)))) (if (safe-queen-p q queens) (find-queens (cons q queens)))))))) (defun return-queens () (let ((solutions nil)) (labels ((find-queens1 (queens) (let ((col (1+ (list-length queens)))) (if (> col 8) (push queens solutions) (loop for row from 1 upto 8 as q = (make-square :col col :row row) when (safe-queen-p q queens) do (find-queens1 (cons q queens))))))) (find-queens1 '()) solutions))) (defun safe-queen-p (q1 queens) (notany #'(lambda (q2) (attack-p q1 q2)) queens)) (defun attack-p (q1 q2) "determine if two queens in positions q1, q2 are attacking each other" (declare (square q1 q2)) (or (= (square-col q1) (square-col q2)) (= (square-row q1) (square-row q2)) (= (abs (- (square-col q2) (square-col q1))) (abs (- (square-row q2) (square-row q1)))))) ```