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 '())

(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))))))


Leave a Comment »

No comments yet.

RSS feed for comments on this post.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: