eight queens problem

Solution Preview

Before all, I would like to invite you to read the following 3 items

# There are 12 solutions.
# In each solution, there are four queens on dark squares and four queens on light squares.
# Just two of the twelve solutions have a queen in a corner

you can also find a full code of this problem below.

To run, simply load file and type (queen n) where
;;;n is the width of board.

;discovers if a piece threatens another
(defun threat (i j a b)
(or (= i a)
(= j b)
(= (- i j) (- a b))
(= (+ i j) (+ a b))))

;discovers if a placement is OK
(defun conflict (n m board)
(cond ((endp board) nil)
((threat n
m
(first (first board))
(second (first board)))
t)
(t (conflict n m (rest board)))))

;;this now prints a board no matter what order it is presented in
(defun print-board (board)
; (sort board #'<= :key #'car)
(format t "~%*")
(print-horizontal-border board)
(format t "*")
(dotimes (row (length board))
(format t "~%|")
(dotimes (column (length board))
(if (= column (second (assoc row board)))

(format t " Q")
(format t " .")))
(format t " |"))
(format t "~%*")
(print-horizontal-border board)
(format t "*"))

(defun print-horizontal-border (board)
(dotimes (n (+ 1 (* 2 (length board))))
(format t "-")))

;;;The following is Winston/Horn's original queen-finding algorithm.
;;;It does not discriminate sets of solutions that are closed under rotation
;;;and reflection. Thus, a single solution can be equivalent to up to 8 other
;;;solutions.

(defun queen* (size &optional (board nil) (n 0) (m 0))
(unless (= m size)
;;Check for conflict in current row and column
(unless (conflict n m board)
(if (= (+ 1 n) size)
;;If all queens placed, prin solution:
(print-board (reverse (cons (list n m) board)))
;;Otherwise, proceed to next row:
(queen* size (cons (list n m) board) (+ 1 n) 0)))
;;In any case, try with another column
(queen* size board n (+ 1 m))))

;;; This version improves on Winston/Horn in that it displays only one instance
;;;of a closed set of solutions. Thus, 8-queens solution is reduced from 96 to 12.
;;;It achieves this by using a bindings list of already-found solutions. Since a change
;;;made at a deeper level of recursive search must be accessible to a higher level,
;;;the bindings list was made a global parameter that ...